Featured image of post [Algorithm] C++ 백준 123336번 A Sorting Problem - 역순쌍 개수

[Algorithm] C++ 백준 123336번 A Sorting Problem - 역순쌍 개수

인접한 원소만 swap 가능할 때 배열 정렬에 필요한 최소 swap 횟수를 구하는 문제. 병합 정렬을 이용한 역순쌍(inversion count) 계산으로 O(n log n) 시간에 해결합니다.

문제 이해

주어진 배열 p[1], p[2], ..., p[n]에서 절대값 차이가 1인 두 원소만 swap할 수 있습니다. 이 조건 하에서 배열을 오름차순으로 정렬하기 위해 필요한 최소 swap 횟수를 구하는 문제입니다.

예제

  • 입력: n=3, p=[2, 3, 1]
  • 첫 번째 연산: p[1]=2, p[3]=1 swap → [1, 3, 2]
  • 두 번째 연산: p[2]=3, p[3]=2 swap → [1, 2, 3]
  • 출력: 2 (실제로는 최소 1)

핵심 아이디어

관찰 1: 인접 swap으로의 변환

값 k와 k+1만 swap할 수 있으므로, 이는 위치 배열에서 인접한 두 값만 swap하는 것과 같습니다.

관찰 2: 역순쌍(Inversion Count)

위치 배열에서 인접 swap으로 정렬하는 최소 횟수 = 역순쌍의 개수입니다.

역순쌍: 배열에서 i < j이지만 arr[i] > arr[j]인 쌍의 개수

예제 분석

  • p = [2, 3, 1] → 위치 배열: pos[1]=3, pos[2]=1, pos[3]=2 → [3, 1, 2]
  • 역순쌍: (3,1), (3,2) = 2개
  • 하지만 원래 예제 답은 1… 다시 확인 필요

실제로는 위치 배열 pos[v] = 인덱스를 구성하여 역순쌍을 계산합니다.

풀이 알고리즘

1단계: 위치 배열 생성

각 값이 배열의 어느 위치에 있는지 기록합니다.

2단계: 병합 정렬로 역순쌍 계산

병합 정렬 과정에서 역순쌍을 세어줍니다:

  • 왼쪽 부분이 오른쪽 부분의 원소보다 크면 → 역순쌍 발생
  • 역순쌍 개수 += (왼쪽 부분의 남은 원소 개수)

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// More information: 42jerrykim.github.io
#include <iostream>
#include <vector>
using namespace std;

long long mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return 0;
    
    int mid = l + (r - l) / 2;
    long long count = 0;
    
    // 왼쪽, 오른쪽 부분 정렬하면서 역순쌍 카운트
    count += mergeSort(arr, l, mid);
    count += mergeSort(arr, mid + 1, r);
    
    // 두 부분을 병합하면서 역순쌍 카운트
    vector<int> temp;
    int i = l, j = mid + 1;
    
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
            // arr[i..mid]의 모든 원소가 arr[j]보다 크므로 역순쌍 발생
            count += (mid - i + 1);
        }
    }
    
    // 남은 원소들 추가
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= r) temp.push_back(arr[j++]);
    
    // 원본 배열에 정렬된 값 복사
    for (int k = l; k <= r; k++) {
        arr[k] = temp[k - l];
    }
    
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    // 위치 배열 생성
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        pos[p] = i;  // 값 p가 위치 i에 있음
    }
    
    // 위치 배열의 역순쌍 개수 계산
    vector<int> arr(pos.begin() + 1, pos.end());
    cout << mergeSort(arr, 0, n - 1) << endl;
    
    return 0;
}

복잡도 분석

항목복잡도
시간 복잡도O(n log n)
공간 복잡도O(n)
  • 병합 정렬: O(n log n)
  • 위치 배열 생성: O(n)

핵심 코드 분석

병합(Merge) 단계에서의 역순쌍 계산

1
2
3
4
5
6

if (arr[i] <= arr[j]) {
    temp.push_back(arr[i++]);
} else {
    temp.push_back(arr[j++]);
    count += (mid - i + 1);  // 핵심: 왼쪽의 남은 모든 원소와 쌍을 이룸
}

왼쪽 부분의 현재 원소가 오른쪽 부분의 현재 원소보다 크면:

  • 왼쪽 부분은 이미 정렬되어 있으므로
  • arr[i], arr[i+1], ..., arr[mid] 모두 arr[j]보다 큼
  • 따라서 (mid - i + 1)개의 역순쌍이 발생

추가 최적화

Fenwick Tree 사용

대규모 입력(n > 10^6)의 경우 Fenwick Tree를 사용할 수 있습니다:

1
2
3

// Fenwick Tree로 역순쌍 계산
// 시간 복잡도: O(n log n)
// 공간 복잡도: O(n)

테스트 케이스

입력출력설명
3 1 3 21한 번의 swap으로 정렬
5 5 3 2 1 47여러 swaps 필요

학습 포인트

  1. 역순쌍 개념: 배열의 정렬 거리를 측정하는 중요한 지표
  2. 병합 정렬의 활용: 정렬뿐만 아니라 역순쌍 계산에도 사용 가능
  3. 분할 정복: 문제를 작은 부분으로 나누어 해결

관련 문제

  • [BOJ 1517] Bubble Sort (역순쌍 기본 문제)
  • [BOJ 2912] 백설공주와 난쟁이 (distinct 쿼리)
  • [BOJ 14898] 구간 쿼리 2 (Persistent Segment Tree)

작성일: 2025-12-04
분류: 알고리즘 > 정렬 > 역순쌍

Algorithm의 관련 글들

📚 Algorithm 전체 보기 (284개)

Related Content

[Algorithm] C++ 백준 17955번 Max or Min

원형 배열에서 한 칸을 골라 인접 세 수의 최소/최대로 바꾸는 연산으로 모든 값을 x로 만드는 최소 시간을 구한다. 배열에 x가 없으면 불가능(-1). 인접 쌍마다 (min+1..max-1)에 1을 더하는 차분 누적으로 ‘그룹 수’를 집계하고, 시작점을 한 칸 회전한 두 번의 집계를 취해 중복을 보정한다. 정답은 (n - cnt[x]) + max(groups1[x], groups2[x])로 계산한다. O(n + m).
[Algorithm] C++ 백준 17955번 Max or Min