[C++][백준] 10090 Counting Inversions

이번 문제는 병합정렬(Merge sort)를 이용해서 해결하는 문제입니다.

 

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.
Two integers in а permutation form an inversion, when the bigger one is before the smaller one.
As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.
Write program invcnt that computes the number of the inversions in a given permutation.

 

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

 

출력

Write the count of inversions on the standard output.

 

독자분들의 영어 실력을 이미 출중하다고 생각하기 때문에 해석은 따로 하진 않겠습니다.

해석하셨다면 아시다시피 주어진 리스트에서 순서가 꼬인, 즉 inversion의 개수를 세는 문제입니다.

 

문제를 해결하기 위해서는 어떤 방법을 쓸 수 있을까?

 

• 단순히 반복문을 여러개 써서 본인보다 작은게 뒤에 나오면 cnt +1 해주고, 아니면 넘어가는 방법도 있을것이다.
• 그러나 이 방법을 사용하면 최소 O(n2)의 시간복잡도가 나올 것이다.
• 물론 이 문제가 브론즈 5정도의 아주 쉬운 문제였다면 성공했을지도 모르겠지만, 이 문제는 플레5에 1000000까지의 범위를 요구하므로 100% 시간초과가 나올 것이다.

일단 문제를 다른 방법으로 분석해보자.

이런 식으로 정렬과정에서 교점의 개수가 곧 inversion의 개수라는 것을 알 수 있다.

 

문제를 해결하기 위해서 병합정렬을 이용할 것이다.

 

병합정렬은 무엇일까?

병합정렬(Merge sort)는 분할정복 알고리즘 중 하나로 O(nlogn)의 비교 기반 정렬 알고리즘이다.
과정을 아래와 같다.

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것과 같으므로)
2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.

 

위 그림을 보면 이해가 편할 것이다.

 

문제 분석을 위한 그림을 병합정렬이라고 생각하고 봤을 때, 0~3 인덱스를 왼쪽, 4~7 인덱스를 오른쪽 배열이라고 하자.

오른쪽 인덱스에서 정렬이 일어날 때는 inversion이 일어나지 않지만, 왼쪽 인덱스에서 정렬이 일어날 때는 오른쪽에서 정렬된 개수만큼 inversion 개수가 증가하는 것을 볼 수 있다.

 

이 두가지 요소를 이용해서 코드를 작성해보자.

#include<bits/stdc++.h>
using namespace std;
constexpr long long MAX = 1000000;
long long arr[MAX];
long long total=0;

void mergesort(long long start, long long end, long long mid, long long arr[]){
    static long long buf[MAX];
    long long i=start, j=mid+1, pointer = start, cross=0;
    while(i<= mid && j<= end){
        if(arr[i]<arr[j]) {
            buf[pointer++] = arr[i++];
            total += cross;
            }
        else {
            buf[pointer++] = arr[j++];
            cross+=1;
        }
    }
    while(i<=mid){
        buf[pointer++] = arr[i++];
        total+= cross;
    }
    while(j<=end) {
        buf[pointer++] = arr[j++];
        cross+=1;
    }
    for(long long k=start; k<=end; k++)
        arr[k] = buf[k];
    return;
}
void merge(long long start, long long end, long long arr[]){
    if(start==end)
        return;
    long long mid = (start+end)/2;
    merge(start,mid,arr);
    merge(mid+1,end,arr);
    mergesort(start,end,mid,arr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N;
    cin >> N;
    for(long long i=0; i<N; i++){
        cin >> arr[i];
    }
    merge(0,N-1,arr);
    cout << total;
    return 0;
}

 

Merge라는 함수와 Mergesort라는 함수를 선언해주었다. 

 

Merge함수는 배열의 길이를 절반씩 분할해주는 함수이다.

• 절반을 기준으로 분할하고, 다시 분할 함수를 호출한다.
• 크기가 1인 상태가 되면 분할을 마친다.

Mergesort함수는 이름처럼 정렬을 실행하는 함수이다.

• 가운데를 기준으로 i는 배열의 처음부터 가운데까지, j는 가운데부터 끝까지를 가리키는 역할을 한다.
• i와 j가 모두 해당 범위에 있으면 작은 애들 순서대로 정렬을 진행한다.
• 결론적으로 i와 j 중 하나는 먼저 범위를 벗어나게 된다. 분할된 배열은 이미 정렬된 상태이기 때문에 남은 원소를 순서대로 병합된 배열에 할당한다.

추가적으로 왼쪽에서 정렬이 일어나는 경우 오른쪽에서 이동한 개수만큼 더해주었고, 반대의 경우는 오른쪽에서 이동한 개수를 세는 변수인 cross를 +1해주었다.