C++로 L번째·R번째로 작은 숫자의 절대 차이를 구하는 쿼리 처리 방법

이 문제에서는 크기가 n인 배열 arr[]와 각각 두 값 L, R로 이루어진 Q개의 쿼리가 주어집니다. 우리가 만들어야 할 프로그램은 각 쿼리에 대해 L번째로 작은 숫자와 R번째로 작은 숫자 사이의 절대 차이를 반환하는 것입니다.

문제 설명

각 쿼리를 해결하려면 먼저 L번째로 작은 원소와 R번째로 작은 원소가 원본 배열에서 어느 인덱스에 위치하는지 찾아야 합니다. 그런 다음 두 인덱스의 차이(절댓값)를 계산하면 됩니다.

예제로 문제 이해하기

입력

arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}}

출력

1 2

설명

{2, 4} 쿼리: 2번째로 작은 원소는 2이고, 그 인덱스는 4입니다. 4번째로 작은 원소는 5이고, 그 인덱스는 3입니다. 차이 = |4 - 3| = 1 {1, 5} 쿼리: 가장 작은 원소는 1이고, 그 인덱스는 2입니다. 5번째로 작은 원소는 8이고, 그 인덱스는 0입니다. 차이 = |2 - 0| = 2

해결 접근 방법 1: pair 자료구조 활용

이 문제를 해결하는 첫 번째 방법은 배열 원소의 값과 인덱스를 함께 저장하는 pair 배열을 만드는 것입니다. pair 배열을 값 기준으로 오름차순 정렬한 뒤, 각 쿼리의 L과 R에 해당하는 i번째로 작은 원소를 찾고, 두 원소의 인덱스 차이의 절댓값을 출력합니다.

정렬된 pair 배열에서 L번째로 작은 원소는 arrayIndex[L-1]에 위치하므로, 인덱스 조회만으로 빠르게 답을 구할 수 있다는 장점이 있습니다.

구현 예제 코드

#include <bits/stdc++.h> using namespace std; void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) { pair<int, int> arrayIndex[n]; for (int i = 0; i < n; i++) { arrayIndex[i].first = arr[i]; arrayIndex[i].second = i; } sort(arrayIndex, arrayIndex + n); for (int i = 0; i < Q; i++){ int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) ); cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl; } } int main() { int arr[] = { 8, 4, 1, 5, 2 }; int n = sizeof(arr) / sizeof(arr[0]); int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }}; solveAllQueries(arr, n, Q, queries); return 0; }

출력 결과

For Query 1: Difference is 1 For Query 2: Difference is 2

해결 접근 방법 2: 정렬된 별도 배열 활용

pair 자료구조를 사용하지 않고도 같은 결과를 얻을 수 있습니다. 이 방법에서는 원본 배열의 값을 오름차순으로 정렬해 저장하는 별도의 배열 minArray를 사용합니다.

동작 과정은 다음과 같습니다.

① 원본 배열 arr[]를 복사하여 minArray를 만들고 정렬합니다.
② 각 쿼리마다 minArray[L-1]과 minArray[R-1]로 L번째, R번째로 작은 값을 구합니다.
③ 해당 값들이 원본 배열 arr[]에서 위치한 인덱스를 탐색(searchEle 함수)합니다.
④ 두 인덱스 차이의 절댓값을 반환합니다.

구현 예제 코드

#include <bits/stdc++.h> using namespace std; int searchEle(int arr[], int ele, int n){ for(int i = 0; i < n; i++) if(arr[i] == ele) return i; return -1; } int findDifference(int arr[], int minArray[], int n, int L, int R){ int Lele = minArray[L-1]; int Rele = minArray[R-1]; int index1 = searchEle(arr, Lele, n); int index2 = searchEle(arr, Rele, n); return abs(index1 - index2); } void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) { int minArray[n]; for (int i = 0; i < n; i++) minArray[i] = arr[i]; sort(minArray, minArray + n); for(int i = 0; i < Q; i++){ cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n, queries[i][0], queries[i][1])<<endl; } } int main() { int arr[] = { 8, 4, 1, 5, 2 }; int n = sizeof(arr) / sizeof(arr[0]); int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }}; solveAllQueries(arr, n, Q, queries); return 0; }

출력 결과

For Query 1: Difference is 1 For Query 2: Difference is 2

두 방법의 비교 및 시간 복잡도

방법 1(pair 활용): 정렬에 O(n log n), 각 쿼리 처리는 O(1)이므로 전체 시간 복잡도는 O(n log n + Q)입니다. pair에 값과 인덱스를 함께 저장하기 때문에 추가 탐색 없이 즉시 답을 구할 수 있어 쿼리가 많은 경우 효율적입니다.

방법 2(정렬 배열 활용): 정렬에 O(n log n), 각 쿼리마다 원본 배열에서 값을 선형 탐색하므로 O(n)이 걸려 전체 시간 복잡도는 O(n log n + Q × n)입니다. 대신 pair를 사용하지 않아 구현이 단순하다는 장점이 있습니다.

따라서 쿼리 개수가 많다면 방법 1을, 메모리나 구현 단순성이 중요하다면 방법 2를 선택하는 것이 좋습니다.