[백준]10090번 inversion counting - C/C++

https://www.acmicpc.net/problem/10090

10090번: Counting Inversions

---

문제

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.

---

완전 탐색으로 i 번째 원소 뒤에 있는 것들 중 나보다 작은 것을 찾게 된다면 O(N^2)의 시간이 걸리게 된다. 그렇기 때문에 NlogN 혹은 N의 시간의 풀이법을 찾아야 한다. 이때 중요한 것이 문제는 '비교'를 하는 것이기 때문에 정렬과 연관지어 생각해볼 수 있다. 특히 mergesort의 경우 정렬된 두 그룹(left / right )을 비교해서 정렬된 한 그룹을 만드는 것으로 right에 있는 그룹의 숫자가 앞으로 가게 된다면 left 의 남아 있는 숫자는 해당 숫자보다 모두 크게 되므로 inversion 이 되어있었다고 볼 수 있다.  

#include <iostream>

using namespace std;

int arr[1000002];
int tmp[1000002];
long long ans=0;

void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) >> 1;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);

        int left = start, right = mid + 1;
        int idx = start;


        while (left <= mid || right <= end) {
            if (right > end || (left <= mid && arr[left] < arr[right])) {
                tmp[idx++] = arr[left++];
            }
            else {
                ans += (mid - left + 1);
                tmp[idx++] = arr[right++];
            }
        }
        for (int i = start; i <= end; i++)
            arr[i] = tmp[i];
    }
}
int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    mergeSort(0, n - 1);
    cout << ans;

    return 0;
}

---

문제의 답을 보고 mergesort 인것을 알게 되었다. 코드를 설계할 때 N^2 이 안되므로 더 좋은 것을 찾아야하는데 비교를 해야하는 것이므로 정렬을 생각해낼 수 있다면 쉽게 풀 수 있는 문제지만 이것을 생각해내지 못했다면 풀지 못했을 것 같다. SWEA에 문제가 있어 풀고 백준에도 문제가 있나 찾아보고 제출하게 된 문제이다! 직접 풀지는 못했지만 많은 것을 느낀 문제이다.