Merge Sort: Counting Inversions

def merge(counter, sourceArr, tempArr, start, mid, end):
    leftIndex = start
    rightIndex = mid + 1
    targetIndex = start

    for i in range(start, end+1):
        tempArr[i] = sourceArr[i]

    while leftIndex <= mid and rightIndex <= end:
        if tempArr[leftIndex] <= tempArr[rightIndex]:
            sourceArr[targetIndex] = tempArr[leftIndex]
            leftIndex += 1
        else:
            sourceArr[targetIndex] = tempArr[rightIndex]
            rightIndex += 1
            counter[0] += (mid - leftIndex + 1)

        targetIndex += 1

    for i in range(0, mid - leftIndex+1):
        sourceArr[targetIndex + i] = tempArr[leftIndex + i]

def mergeSort(counter, sourceArr, tempArr, start, end):
    if start < end:
        mid = (start + end) // 2
        mergeSort(counter, sourceArr, tempArr, start, mid)
        mergeSort(counter, sourceArr, tempArr, mid + 1, end)
        merge(counter, sourceArr, tempArr, start, mid, end)

# Complete the countInversions function below.
def countInversions(arr):
    length = len(arr)
    tempArr = [0] * length
    counter = [0]

    mergeSort(counter, arr, tempArr, 0, length-1)

    return counter[0]

 

해당 문제는 제목에서 어떻게 해결하라는걸 알려주고 시작한다.

Merge sort(합병정렬)을 이용해서 문제를 풀면 되는데 기본적으로 합병정렬을 구현해 놓는다.

 

구현해 놓은 합병정렬에서 교환하는 부분만 찾아낸 다음에 해당 로직 안에서 카운터를 증가시켜주면 되는 간단한 문제이다.

합병 정렬에서 실제로 교환이 일어나는 부분은 우측에 있는 값이 좌측에 있는 값 보다 작을 경우 일어난다. 좌측에 있는 값이 더 작은 경우는 오름차순 정렬 상 자신의 자리에 있기 때문이다.

카운터를 배열로 선언한 이유는 파이썬에는 포인터가 없어서 call by value가 아닌 call by ref로 넘겨주는 방법이 객체타입을 사용하는 방법만 있기 때문이다.