[Python] Codility ArrayInversionCount

An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].

 

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

 

당연히 하나씩 비교했을 시 O($N^{2}$)이 되므로 이를 개선할 필요성이 있다.

이 때 보통 병합정렬(merge sort)을 사용한다.

 

병합정렬은 분할(divide), 정복(conquer), 결합(combine) 3가지 step으로 문제를 해결하는 것이다.

 

def solution(A):
    def merge_sort(arr):
    	if len(arr) <= 1:
            return arr, 0

        mid = len(arr)//2
        left, inv_left = merge_sort(arr[:mid])
        right, inv_right = merge_sort(arr[mid:])
        merged, inv_split = merge_and_count(left, right)
        
        total_inversions = inv_left + inv_right + inv_split
        
        if total_inversions > 1000000000:
            return merged, -1
        return merged, total_inversions
    
    def merge_and_count(left, right):
        merged = []

        i = j = inversions = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                inversions += len(left) - i # Left[i:]는 전부 right[j]보다 크닌까 inversion 발생
                j += 1

        merged += left[i:]
        merged += right[j:]
        return merged, inversions

    _, count = merge_sort(A)
    return count if count != -1 else -1