[Hackerrank in C] counting inversions

문제

https://www.hackerrank.com/challenges/ctci-merge-sort/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

Merge Sort: Counting Inversions | HackerRank

 

풀이

minimum swaps 2 와 비슷한 문제라 비슷한 방식으로 풀면 되겠지 라고 생각했지만,

minimum swaps 2에서는 숫자가 한번씩 반복되며, 착하게 1에서부터 n 까지 나온다.

하지만 이 문제는 여러 숫자가 반복되면서 나올 수 있으므로 완전히 다른 문제다.

 

# of inversions를 세는건 # of swaps = # of when left number > right number. 을 세는 것과 같다.

 

for example, when arr = [2,1,3,1,2], there are 4 inversions.

for swaping (2,1) , (2,1), (3,1), (3,2)

 

물론 2d for loop으로 찾을 수 도 있지만,

문제 이름 그대로 merge sort을 사용하면 nlog(n) 걸리게 되므로 시간이 짧아진다.

 

왜 merge sort인가?

merge sort는 arr의 left & right parts 를 비교하면서 left > right 이 되는 때를 찾기때문.

한마디로, merge sort uses divide and conquer alignment. 

 

코드

void merge(int* arr, int left, int mid, int right, long* count) { // count = #swaps (when L > R)
    int size_l = mid - left + 1; // include mid;
    int size_r = right - mid;
    
    int* L = (int*)malloc(size_l * sizeof(int));
    int idx = 0;
    for(int i=left; i<=mid; i++) {
        L[idx++] = arr[i];
    }
    int* R = (int*)malloc(size_r * sizeof(int));
    idx = 0;
    for(int i=mid+1; i<=right; i++) {
        R[idx++] = arr[i];
    }
    
    int i_l = 0, i_r=0, i=left;
    while(i_l<size_l && i_r<size_r) {
        if(L[i_l] > R[i_r]) {
            (*count) += (size_l - i_l); // when arr = [2, 1, 3, 0, 2], swap(2,1) + (2,0) = two!
            arr[i++] = R[i_r++];
        } else {
            arr[i++] = L[i_l++];
        }
    }
    while(i_l<size_l) {
        arr[i++] = L[i_l++];
    }
    while(i_r<size_r) {
        arr[i++] = R[i_r++];
    }
    
    free(L);
    free(R);
    
}
void mergeHelper(int* arr, int left, int right, long* count) {
    if(left >= right) return ;
    int mid = left + (right-left)/2;
    mergeHelper(arr, left, mid, count);
    mergeHelper(arr, mid+1, right, count);
    merge(arr, left, mid, right, count);
}
long countInversions(int arr_count, int* arr) {
    long count = 0;
    mergeHelper(arr, 0, arr_count-1, &count);
    
    return count;
}