백준 10090번 문제 Counting Inversions 문제 풀이

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

백준저지 10090번 문제 Counting Inversions라는 문제이다.

나름 유명한 문제라고 한다.

수열이 있을때 자신보다 앞에있는 숫자 중에 자신보다 큰 녀석을 Inversion이라고 하는데 그 Inversion의 개수를 구하는 문제이다.

Brute force로 풀면 //(O(N^2)//)로 풀게 되는데 그럴 경우 당연 TLE가 나게 된다. 이보다 효율적인 알고리즘이 필요하다.

이 문제는 Merge sort를 응용해서 풀 수 있다.

Merge sort에서 Merge를 수행할 때, 인접한 왼쪽 부분배열과 오른쪽 부분배열을 Merge 할 것이다.

Merge 하기 직전에 왼쪽 부분배열의 모든 원소는 오른쪽 부분배열의 모든 원소보다 원래 왼쪽에 있었다는 것은 자명하다.

그래서 Merge를 할때 오른쪽 배열에 있는 원소가 임시 배열로 들어갈 때, 왼쪽 배열에서 아직 임시 배열에 들어가지 않은 경우

왼쪽배열에 아직 남아있는 원소는 방금 들어간 오른쪽 배열에 있던 원소보다는 다 크기가 크다는 이야기가 된다.

고로 Merge Sort응용으로 //(O(NlgN)//)으로 풀 수 있다.

 

#include <stdio.h>
#include <malloc.h>

int arr[1000005];
int tmp[1000005];

typedef long long ll;
ll ans;
void merge(int start, int mid, int end) { // [start, mid) [mid, end)
    int p1, p2, index = 0;
    p1 = start;
    p2 = mid;
    while (p1 < mid && p2 < end) {
        if (arr[p1] < arr[p2]) {
            tmp[index++] = arr[p1++];
        }
        else if (arr[p1] > arr[p2]) {
            ans += mid - p1;
            tmp[index++] = arr[p2++];
        }
        else {
            tmp[index++] = arr[p2++];
        }
    }
    while (p1 < mid) {
        tmp[index++] = arr[p1++];
    }
    while (p2 < end) {
        tmp[index++] = arr[p2++];
    }
    for (int i = 0; i < end - start; ++i) {
        arr[start + i] = tmp[i];
    }
}

void merge_sort(int start, int end) { // [start, end)
    int mid = (start + end) / 2;
    if (start < mid) {
        merge_sort(start, mid);
        merge_sort(mid, end);
        merge(start, mid, end);
    }    
}

int main() {

    ans = 0;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }

    merge_sort(0, n);
    printf("%lld\n", ans);

    return 0;
}

Reference

https://www.geeksforgeeks.org/counting-inversions/