백준 / 1517(버블소트) / python

버블 소트의 swap 횟수를 찾는 문제인데

merge 할 때 왼쪽 오른쪽으로 구분되는 부분에서 오른쪽에 있는게 먼저 삽입이 될 때
왼쪽에 있는 리스트들의 수 만큼 답이 증가가 된다.

swap은 몇 번 될까?

일단 bubble sort에서 swap이 몇번 되는지를 보면 나보다 앞에 있는 숫자 중 나보다 큰 수는 몇개인지? 확인하는 문제이다.

그런데 merge sort를 하다보면 그 과정이 자연스럽게 이뤄지는데

6 5 4 3 2 1 이렇게 있다고 한다면

마지막에
[4 5 6 ][ 1 2 3] 이렇게 되고

[4 5 6][2 3]
새로운 배열 : [1]
이렇게 삽입이 될텐데
1이 삽입이 될 때 왼쪽에 4 5 6 자기 자신 보다 큰 수가 몇개인지 찾을 수 있다.

더 작은 범위의

3 2 1 에서도

[3][2] / [1] 이렇게 나눠지고 merge할 것이다.

이때 2보다 큰 수 3 이 앞에 있고 왼쪽에 있는 수는 1개
[2 3] / [1]
이렇게 되고 1보다 큰 수는 왼쪽에 있는 숫자의 배열이 된다.

이런식으로 구할 수 있다. 그리고 같은 경우는 swap을 해주면 안되기 때문에
merge할 때 비교하는 부분에 대해서 등호를 붙이는 거에 대해 조금 주의 할 필요가 있다.

from sys import stdin
import sys
sys.setrecursionlimit(10**9)


answer =0 
def merge(left, mid, right, a, tmp):
    global answer
    if left >= right:
        return
    i = left
    j = mid +1
    p = left

    
    while 1:
        if a[i]<=a[j]: # 같을 때!! 이렇게 해서
            tmp[p] = a[i]
            p+=1
            i+=1
        else:
            tmp[p] = a[j]
            p+=1
            j+=1
            answer  += (mid- i + 1)
        
        # 밀어 넣기
        if i >mid:
            while j<=right:
                tmp[p] = a[j]
                p+=1
                j+=1
                break
            break
        
        if j>right:
            while i<=mid:
                tmp[p] = a[i]
                p+=1
                i+=1
            break
    
    # 복사하기
    for w in range(left, right+1):
        a[w] = tmp[w]
    
        

def merge_sort(left : int, right : int, a, tmp):
    if left >=right:
        return
    
    mid = (left + right)//2
    
    merge_sort(left, mid, a, tmp) # left side
    merge_sort(mid+1, right, a, tmp) # right side
    merge(left, mid, right, a, tmp) # merge
    
    
if __name__ =='__main__':
    n = int(input())
    li = list(map(int, stdin.readline().split()))
    tmp = [0]*len(li)
    merge_sort(0, len(li)-1, li, tmp)

    print(answer)