[Jungol] 정올 1814 삽입정렬 횟수 세기

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1087&sca=2070

Approach

숫자의 개수가 크지 않은 N이었다면, 실제 삽입 정렬을 구현해서 교환(밀어내기) 횟수를 구해도 되지만,

삽입 정렬의 시간복잡도는 O(N2)이기 때문에 숫자 개수 N이 클 경우 TLE 발생

 

이 문제는 삽입정렬을 구현하여, 특정 숫자가 삽입 될 때, 교환 횟수를 물어보는 것이 아니라

정렬이 끝난 후, 총 교환 횟수를 요구하고 있습니다. (그 과정에서 삽입정렬 방식이 설명되어 있는 것입니다.)

따라서 시간복잡도 O(NlogN) 많은 숫자 개수 N에서도 가능합니다.

 

Merge Sort에서 교환횟수는 어떻게 구할 수 있을까?

정렬되지 않은 숫자 { 4  3  5  2  1 }가 존재할 때, merge 되는 과정을 살펴보겠습니다.

① {4, 3} {5} {2, 1} → {3, 4} {5} {1, 2}

    3이 앞에 와서 4가 밀렸습니다.

    1이 앞에 와서 2가 밀립니다.

② {3, 4, 5} {1, 2} → {3, 4, 5} {1, 2}

    변화가 없습니다.

③ {3, 4, 5, 1, 2} → {1, 3, 4, 5, 2} → {1, 2, 3, 4, 5}

    1이 앞에 오면서 3, 4, 5가 밀렸습니다.

    2가 앞에 오면서 3, 4, 5가 밀렸습니다.

▶총 1 + 1 + 3 + 3 = 8번 발생

ans += (mid - i + 1); 로도 가능

* N이 큰 경우에는 ans 타입을 long long으로 선언

---

#include <stdio.h>
 
const int MAX_N = 1e5;
int arr[MAX_N + 5], temp[MAX_N + 5];
int n;
long long ans;
 
void mergeSort(int start, int end) {
    if (start >= end)
        return;
 
    int mid = (start + end) / 2;
 
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
 
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] > arr[j]) {
            ans += (j - k);
            temp[k++] = arr[j++];
        }
        else {
            temp[k++] = arr[i++];
        }
    }
 
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= end) temp[k++] = arr[j++];
 
    for (i = start; i <= end; i++)
        arr[i] = temp[i];
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    ans = 0;
    mergeSort(0, n - 1);
    printf("%lld\n", ans);
}