C++ STL pair를 활용해 다른 배열 기준으로 배열 정렬하기

두 개의 서로 다른 배열이 있을 때, C++ STL의 pair 클래스를 이용하면 한 배열을 다른 배열의 값에 맞춰 함께 정렬할 수 있습니다. 예를 들어 첫 번째 배열 A1 = [2, 1, 5, 4, 9, 3, 6, 7, 10, 8]과 두 번째 배열 A2 = [A, B, C, D, E, F, G, H, I, J]가 있다고 가정해 보겠습니다. 정렬 후 결과는 다음과 같습니다.

A1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
A2 = [B, A, F, D, C, G, H, J, E, I]

핵심 아이디어

이 문제의 핵심은 pair를 활용하는 것입니다. A1의 요소를 first로, A2의 대응되는 요소를 second로 하여 pair 배열을 만듭니다. 그런 다음 표준 sort 함수를 호출하면 됩니다. 이때 주의할 점은 first(첫 번째 요소)를 기준으로 정렬이 수행된다는 것입니다. 즉, 어떤 배열을 기준으로 정렬할지에 따라 pair의 first와 second에 배치할 배열을 적절히 선택해야 합니다.

C++ STL에서 pair는 기본적으로 first 값을 먼저 비교하고, first가 같으면 second 값을 비교하여 정렬합니다. 따라서 별도의 비교 함수(comparator) 없이도 간단하게 구현할 수 있습니다.

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;

template <class T>
void display(T arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

void sortUsingSecondArr(int A1[], char A2[], int n) {
    // A1을 first, A2를 second로 하는 pair 배열 생성
    pair<int, char> pair_arr[n];
    for (int i = 0; i < n; i++) {
        pair_arr[i].first = A1[i];
        pair_arr[i].second = A2[i];
    }

    // first(A1의 값)를 기준으로 정렬
    sort(pair_arr, pair_arr + n);

    // 정렬된 값을 원래 배열에 되돌려 저장
    for (int i = 0; i < n; i++) {
        A1[i] = pair_arr[i].first;
        A2[i] = pair_arr[i].second;
    }
}

int main() {
    int n = 10;
    int A1[] = {2, 1, 5, 4, 9, 3, 6, 7, 10, 8};
    char A2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};

    cout << "Before Sorting: " << endl;
    cout << "First Array : "; display(A1, n);
    cout << "\nSecond Array: "; display(A2, n);

    sortUsingSecondArr(A1, A2, n);

    cout << "\n\nAfter Sorting: " << endl;
    cout << "First Array : "; display(A1, n);
    cout << "\nSecond Array: "; display(A2, n);
}

실행 결과

Before Sorting:
First Array : 2 1 5 4 9 3 6 7 10 8
Second Array: A B C D E F G H I J

After Sorting:
First Array : 1 2 3 4 5 6 7 8 9 10
Second Array: B A F D C G H J E I

동작 방식 설명

정렬 전에는 A1의 값 2와 짝을 이루던 문자가 'A', 값 1과 짝을 이루던 문자가 'B'였습니다. pair 배열을 만들면 (2, 'A'), (1, 'B'), (5, 'C'), ... 형태로 저장됩니다. sort 함수가 first 값을 기준으로 오름차순 정렬하기 때문에 (1, 'B'), (2, 'A'), (3, 'F'), ... 순서로 재배열됩니다. 마지막으로 pair의 값을 다시 원래 배열에 복사하면 A1은 오름차순으로 정렬되고, A2는 A1의 원래 위치 관계를 그대로 유지한 채 함께 정렬됩니다.

참고 사항

- 시간 복잡도는 표준 sort 알고리즘을 사용하므로 O(n log n)입니다.
- 가변 길이 배열(VLA)인 pair<int, char> pair_arr[n]은 GCC 등 일부 컴파일러에서만 지원되므로, 이식성을 높이려면 vector<pair<int, char>>를 사용하는 것이 좋습니다.
- 반대로 A2를 기준으로 정렬하고 싶다면 pair의 first에 A2의 값을 넣으면 됩니다.