C++에서 L번째와 R번째로 작은 숫자의 인덱스 절대 차이를 구하는 쿼리 처리 방법

이 튜토리얼에서는 L번째로 작은 숫자와 R번째로 작은 숫자가 배열에서 위치한 인덱스 간의 절대 차이를 반환하는 쿼리를 처리하는 프로그램을 살펴봅니다.

정수로 이루어진 배열과 Q개의 쿼리가 주어졌을 때, 각 쿼리 (L, R)에 대해 배열에서 L번째로 작은 값의 인덱스와 R번째로 작은 값의 인덱스 사이의 절대 차이를 구하는 것이 목표입니다.

접근 방법

이 문제는 다음과 같은 단계로 효율적으로 해결할 수 있습니다.

배열의 각 요소를 (값, 원래 인덱스) 형태의 쌍(pair)으로 저장합니다.
값을 기준으로 배열을 오름차순으로 정렬합니다.
각 쿼리 (L, R)에 대해 정렬된 배열의 L번째 요소와 R번째 요소가 가진 원래 인덱스 차이의 절댓값을 계산하여 출력합니다.

정렬을 한 번만 수행하기 때문에 이후의 모든 쿼리를 O(1) 시간에 처리할 수 있다는 점이 이 방법의 핵심입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 쿼리 결과를 반환하는 함수
int respondingQuery(pair<int, int> arr[], int l, int r) {
    int result = abs(arr[l - 1].second - arr[r - 1].second);
    return result;
}

// 쿼리를 처리하는 함수
void calcDifference(int givenarr[], int a, int q[][2], int b) {
    pair<int, int> arr[a];
    for (int i = 0; i < a; i++) {
        arr[i].first = givenarr[i];
        arr[i].second = i;
    }
    sort(arr, arr + a);
    for (int i = 0; i < b; i++)
        cout << respondingQuery(arr, q[i][0], q[i][1]) << endl;
}

int main() {
    int arr[] = { 1, 7, 4, 2, 8 };
    int arraySize = sizeof(arr) / sizeof(arr[0]);
    int query[][2] = { { 2, 4 }, { 1, 5 }, { 3, 3 }, { 5, 1 } };
    int querySize = sizeof(query) / sizeof(query[0]);
    calcDifference(arr, arraySize, query, querySize);
    return 0;
}

출력

코드 설명

배열 {1, 7, 4, 2, 8}을 (값, 인덱스) 쌍으로 변환하면 (1,0), (7,1), (4,2), (2,3), (8,4)가 되고, 값을 기준으로 정렬하면 다음과 같습니다.

(1,0), (2,3), (4,2), (7,1), (8,4)

정렬된 배열을 기준으로 각 쿼리의 결과를 살펴보면 다음과 같습니다.

쿼리 (2, 4): 2번째로 작은 값은 2(인덱스 3), 4번째로 작은 값은 7(인덱스 1)이므로 |3 − 1| = 2
쿼리 (1, 5): 1번째로 작은 값은 1(인덱스 0), 5번째로 작은 값은 8(인덱스 4)이므로 |0 − 4| = 4
쿼리 (3, 3): 같은 순위를 가리키므로 |2 − 2| = 0
쿼리 (5, 1): 5번째 값의 인덱스 4와 1번째 값의 인덱스 0의 차이이므로 |4 − 0| = 4

시간 복잡도

정렬: O(N log N)
쿼리당 처리: O(1)
전체: O(N log N + Q)

쿼리 개수가 많더라도 정렬이 미리 완료되어 있기 때문에 각 쿼리를 상수 시간에 처리할 수 있습니다. 단, 쿼리의 L과 R은 항상 배열 크기 범위(1 이상 N 이하) 안에 있어야 배열 범위를 벗어나는 접근을 피할 수 있다는 점에 유의해야 합니다.