병합 정렬(merge sort) 테크닉을 이용한 counting inversion 문제 해결하는 방법

1. counting inversion problem

 

inversion이란 배열 A에 대하여 자기보다 뒤(index가 큰 쪽)에 있으면서 자기보다 값이 작은 A[j]를 뜻한다.

 

수학적으로 i < j이고 A[i] > A[j]를 만족하는 (i,j)의 개수를 세는 문제이다.

 

단순하게 세면 $O(N^{2})$이지만 실제 위치보다 전후 관계만 본다는 점을 관찰한다면,

 

2,X,X,X,X,X,X,X,X,1이더라도 2와 1은 inversion이고, 2,1,X,X,X,X,X,X,X,X,...더라도 2와 1은 inversion이다.

 

또한 다음 그림과 같이 화살표들의 교점의 개수와 동일하다.

 

두 수가 서로 inversion이면 교점이 하나 생기기 때문이다.

 

 

2. 해법

 

위 그림에서 볼 수 있는대로, 병합정렬을 하면 자연스럽게 해결할 수 있다

 

예를 들어 위의 경우 병합정렬을 하는 과정에서 마지막에 [1,3,4,5], [2,6,7,8] 두 배열의 병합과정이 이루어지는데..

 

앞의 과정은 생략하고 이 부분만 생각해보자. 다음 그림에서 나타나는 테크닉이 매우 중요하다.

 

두 부분배열에서 왼쪽과 오른쪽의 인덱스를 이용해서 두 수를 비교한 다음 

 

더 작은 수를 병합 배열에 넣고, 해당 인덱스는 오른쪽으로 옮길 것이다.

 

 

 

이 때 핵심은 오른쪽 배열에서 병합 배열로 이동할 경우, 그 이동 화살표의 개수를 항상 저장하고 있어야한다.

 

1은 먼저 병합배열에 넣고, 다음 오른쪽의 2를 병합배열에 넣을건데 오른쪽에서 이동하면 그 화살표 개수를 1 증가시킨다.

 

 

 

이제 3과 6중에서 더 작은 3을 병합 배열에 넣을건데...

 

이제 왼쪽 배열에서 병합 배열에 넣는 경우, 지금까지 센 오른쪽 화살표의 개수 수만큼 교점 수에 증가시켜준다.

 

그러니까 왼쪽 화살표가 병합 배열로 이동하면 지금까지 만들어진 오른쪽 화살표의 수만큼 교점이 생기는 것이다.

 

6보다 3,4가 작으니 각각 병합 배열에 넣는 순간 다음 그림과 같이 교점이 1개씩 생긴다.

 

 

마찬가지로 5도 6보다 작으니 병합 배열에 넣으면 교점이 1개 생긴다

 

나머지 6,7,8을 이제 병합 배열에 넣어준다.

 

어차피 끝났지만 오른쪽에서 이동할 경우 그 화살표 개수를 1씩 증가시킨다.

 

 

[3,1,4,5,2,6,8,7]에 대해 여기서 3개를 세지만... 내가 [1,3,4,5], [2,6,7,8]부터 시작했기 때문에.. 3개가 나온거고

 

아예 처음부터 병합정렬 과정을 거치면 총 5개가 세질 것이다..

 

 

3. 연습문제

 

7578번: 공장 (acmicpc.net)

7578번: 공장

 

4. 풀이

 

A 배열에 있는 수를 B 배열이 나타내는 위치로 이동시킨다고 생각을 할때, B 배열에 있는 수들을 해당 수들의 index로 대응시킨다.

 

[392,351,132,311,231]이 B배열이므로, B = {392:0,351:1,132:2,311:3,231:4}

 

A 배열을 해당 수들이 B 배열의 어디 index로 이동시켜야하는지 index 배열로 변환시킨다.

 

A = [132,392,311,351,231]이므로 [2,0,3,1,4]로 변환 시켜준다.

 

변환된 index 배열 [2,0,3,1,4]를 merge sort한다.

 

얘를 merge sort한다는 것이 무슨 의미일까?

 

생각해보면 A에 있는 수들이 B에 있는 수의 위치로 이동한다는 뜻이 된다.

 

A = [132,392,311,351,231]을 [392,351,132,311,231]로 만들어야하는데, 132를 2에 대응시켜 sorting하면 132는 배열에서 2번 위치로 갈 것이다.

 

그래서 A > merge sort > B 하면서 이때 생기는 교점의 개수를 세면 inversion의 수를 알 수 있다.

 

 

merge sort할때 오른쪽 배열을 나타내는 j번째 index의 수가 병합 배열로 이동할때, 그 화살표 개수를 1씩 증가시키고,

 

왼쪽 i번째 index의 수가 병합 배열로 이동할때, 그동안 센 화살표 개수만큼 교점 수로 count시켜나가면 된다.

 

#counting inversion
from sys import stdin

def merge(a,start,mid,end):
    
    merged_list = [0]*(end - start + 1)

    i = start
    j = mid + 1
    k = 0

    count = 0
    right = 0

    while i <= mid and j <= end:
        
        if a[i] > a[j]:
            
            merged_list[k] = a[j]
            j += 1
            k += 1
            right += 1 #오른쪽 배열의 수가 병합 배열로 이동하면 화살표 수를 1 증가
        
        else:
            
            #왼쪽 배열의 수가 병합 배열로 이동하면 inversion 수를 지금까지 센 화살표 수만큼 증가
            merged_list[k] = a[i]
            i += 1
            k += 1
            count += right
    
     #왼쪽 배열의 수가 병합 배열로 이동하면 inversion 수를 지금까지 센 화살표 수만큼 증가
    while i <= mid:
        
        merged_list[k] = a[i]
        i += 1
        k += 1
        count += right
    
    #오른쪽 배열의 수가 병합 배열로 이동하면 화살표 수를 1 증가
    #하는데... 여기서는 왼쪽 수는 이미 다 이동했으므로, 더 이상 교점이 안생기니 굳이 안해도 됨
    while j <= end:
        
        merged_list[k] = a[j]
        j += 1
        k += 1
    
    for s in range(start,end+1):
        
        a[s] = merged_list[s-start]
    
    return count

def merge_sort(a,start,end):
    
    global answer

    if start == end:
        
        return

    mid = start + (end - start)//2

    merge_sort(a,start,mid)
    merge_sort(a,mid+1,end)
    
    answer += merge(a,start,mid,end)

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))
B = list(map(int,stdin.readline().split()))

#B 배열 수들의 index를 알아내는 과정
b = {}

for i in range(n):
    
    b[B[i]] = i

#A 배열 수들을 B배열 수들의 index로 변환
a = []

for i in range(n):
    
    a.append(b[A[i]])

answer = 0

#A의 index 배열을 merge sort한다는 것은
#A 배열의 수들을 B배열 수들의 위치로 이동시킨다는 의미
merge_sort(a,0,n-1)

print(answer)

 

근데.. 왜 되는거지 신기하긴 하네