C++로 풀어보는 역순 쌍(Reverse Pairs) 문제 – 병합 정렬 기반 접근법

배열이 하나 주어졌다고 가정해 봅시다. 이 배열에서 두 원소 A[i]와 A[j]가 아래 조건을 만족할 때, 이 쌍을 중요 역순 쌍(important reverse pair)이라고 부릅니다.

• i < j 이고 A[i] > 2 × A[j]

우리가 구해야 할 것은 바로 이러한 중요 역순 쌍의 개수입니다. 예를 들어 입력이 [2, 8, 7, 7, 2]라면 결과는 3이 됩니다.

실제로 조건을 만족하는 쌍은 (8, 2), (7, 2), (7, 2)로 세 가지입니다. 여기서 8은 뒤에 있는 2보다 두 배 이상 크고, 두 개의 7 역시 마찬가지이기 때문입니다.

접근 방식: 병합 정렬 활용하기

단순히 모든 쌍을 비교하는 브루트 포스 방식은 O(n²)의 시간이 걸려 비효율적입니다. 대신 병합 정렬(merge sort)을 응용하면 O(n log n) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 배열을 반으로 나눈 뒤 각각을 정렬하고 병합할 때, 왼쪽 절반과 오른쪽 절반은 이미 정렬된 상태입니다. 따라서 왼쪽 절반의 각 원소 a[i]에 대해 오른쪽 절반에서 a[first] × 2 < a[i]를 만족하는 원소들의 위치를 포인터 first로 추적하면, 해당 원소가 만드는 역순 쌍의 개수를 한 번의 순회로 셀 수 있습니다.

해결 단계

• 정답 변수 ans := 0으로 초기화합니다.
• merge() 함수를 정의합니다. 매개변수는 배열 a, low, mid, high입니다.
  • k := high − low + 1 로 계산하고, 크기가 k인 임시 배열 temp를 만듭니다.
  • i := low, j := mid + 1, k := 0, first := mid + 1 로 초기화합니다.
  • i ≤ mid 인 동안 반복합니다.
    • first ≤ high 이고 a[first] × 2 < a[i] 인 동안 first를 1씩 증가시킵니다.
    • j ≤ high 이고 a[j] ≤ a[i] 인 동안 temp[k] := a[j] 를 저장하고 j, k를 증가시킵니다.
    • ans := ans + first − (mid + 1) 로 현재 원소가 만드는 역순 쌍의 개수를 더합니다.
    • temp[k] := a[i] 를 저장하고 i, k를 증가시킵니다.
  • j ≤ high 인 동안 남은 오른쪽 절반의 원소들을 temp에 복사합니다.
  • temp의 내용을 원래 배열 a의 low부터 high까지 되돌려 씁니다.
• calc() 함수를 정의합니다. 매개변수는 배열 a, low, high입니다.
  • low ≥ high 이면 그대로 반환합니다.
  • mid := low + (high − low) / 2 로 분할 지점을 정합니다.
  • calc(a, low, mid) 와 calc(a, mid + 1, high) 를 재귀 호출합니다.
  • merge(a, low, mid, high) 를 호출해 두 구간을 병합하며 쌍을 셉니다.
• solve() 함수를 정의합니다. 매개변수는 배열 A입니다.
  • ans := 0 으로 초기화하고 n := A의 크기로 설정합니다.
  • calc(A, 0, n − 1) 을 호출한 뒤 ans를 반환합니다.
• 메인 메서드에서는 solve(nums) 를 호출해 결과를 반환합니다.

구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int ans = 0;
    void merge(vector <int> &a, lli low, lli mid, lli high){
        lli k = high - low + 1;
        vector <lli> temp(k);
        lli i = low, j = mid + 1;
        k = 0;
        lli first = mid + 1;
        while(i <= mid){
            while(first <= high && (lli)a[first] * 2 < (lli)a[i]) {
                first++;
            }
            while(j <= high && a[j] <= a[i])
            {
                temp[k] = a[j];
                j++;
                k++;
            }
            ans += first - (mid + 1);
            temp[k] = a[i];
            i++;
            k++;
        }
        while(j <= high){
            temp[k] = a[j];
            k++;
            j++;
        }
        k = 0;
        for(lli i = low; i <= high; i++){
            a[i] = temp[k];
            k++;
        }
    }
    void calc(vector <int> &a, lli low, lli high){
        if(low >= high)return;
        lli mid = low + (high - low)/2;
        calc(a, low, mid);
        calc(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    lli solve(vector<int> &A) {
        ans = 0;
        lli n = A.size();
        calc(A, 0, n - 1);
        return ans;
    }
    int reversePairs(vector<int>& nums) {
        return solve(nums);
    }
};
main(){
    Solution ob;
    vector<int> v = {2,8,7,7,2};
    cout << (ob.reversePairs(v));
}

입력

{2,8,7,7,2}

출력

3

마무리

이처럼 병합 정렬의 병합 과정에 역순 쌍 계산 로직을 결합하면, 모든 쌍을 일일이 확인하지 않고도 O(n log n)의 시간 복잡도로 중요 역순 쌍의 개수를 효율적으로 구할 수 있습니다. 주의할 점은 곱셈 과정에서 값이 커질 수 있으므로 long long 타입을 사용해 오버플로를 방지하는 것이 좋습니다.