[백준알고리즘] 1517번: 버블 소트 -Python

[백준알고리즘] 1517번: 버블 소트 -Python

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

당연히 일반적인 방법으로 문제를 해결할 경우 시간 초과가 발생할 것이란 것을 알고 있었다. 그런데 그거 외에는 방법을 모르겠어서.. 각각의 값마다 앞의 인덱스에서 자신보다 큰 값의 개수를 새는 것까지는 생각했는데 결국 O(N^2)을 벗어날 수 없었다.

# 여기서 앞에 존재하는 큰 값의 개수를 세는, 역순으로 존재하는 수의 개수를 찾는 것을 Inversion Counting이라 한다.

 

빠르게 포기하고 푸는 방법들을 찾아보니 합병 정렬을 사용하거나 인덱스 트리를 사용해서 O(NlogN)에 해결이 가능하다는 것을 알게 되었다.

 

그런데 아무리 찾아도 인덱스 트리를 푸는 방식은 이해가 안됐다... 애초에 인덱스 트리라는 자료구조를 처음 들어봤는데 보다 보니 부분합을 구할 때 유용한 구조로, DP로 부분합을 구하는 방식과 유사했다. 그런데 이 개념을 버블 소트에서 swap 횟수를 구하려고 하니 이해가 안 됐다. 외국의 글들도 찾아봤는데..

 

문제를 풀고 나서 다른 분들의 코드를 봐도... 합병 정렬을 이용한 분들이 대부분이었고, 인덱스 트리를 사용하신 것같은 분들의 코드는 모르는 언어라 머리 아파서 포기했다. ^_^ 나중에 이해하게 되면 다시 풀어봐야겠다.

 

 

결국 merge sort를 이용한 방식으로 해결했다. 결국 swap 횟수를 구하는 것이기 때문에 merge sort를 이용해 swap 횟수를 구하면 되기 때문이다. 여기서 swap횟수는 다양한 방법으로 구할 수 있는데, merge 하는 과정에서 결국 자신보다 앞의 인덱스에서 큰 값의 수를 구하면 되는데 다음과 같이 문제를 해결했다.

 

# merge하는 과정에서 3가지의 리스트를 각각 왼쪽 리스트, 오른쪽 리스트, 새로운 리스트라 부르겠다.

1. 왼쪽 리스트의 값을 새로운 리스트에 채울 경우 swap += cnt

2. 오른쪽 리스트의 값을 새로운 리스트에 채울 경우 cnt += 1

 

위와 같이 식이 나오게 되는 이유는 왼쪽 리스트와 오른쪽 리스트는 각각 정렬된 상태이다. 여기서 왼쪽 리스트의 값이 새로운 리스트에 채워질 경우 앞서 오른쪽 리스트에서 새로운 리스트로 먼저 채워진 수만큼 swap이 진행되었기 때문이다.

반대로 생각하면 오른쪽 리스트의 값이 추가될 경우 왼쪽 리스트에서 새로운 리스트로 채워지지 않은 왼쪽 리스트의 원소의 개수만큼 swap이 진행되기 때문이다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
def merge_sort(start, end):
    global swap, arr
    size = end - start
    mid = (start + end) // 2
    if size <= 1:
        return
 
    # divide
    merge_sort(start, mid)
    merge_sort(mid, end)
 
    # merge
    new_arr = []
    idx1, idx2 = start, mid
    cnt = 0
    while idx1 < mid and idx2 < end:
        if arr[idx1] > arr[idx2]:
            new_arr.append(arr[idx2])
            idx2 += 1
            cnt += 1
        else: # arr[idx1] < arr[idx2]
            new_arr.append(arr[idx1])
            idx1 += 1
            swap += cnt
    
    while idx1 < mid:
        new_arr.append(arr[idx1])
        idx1 += 1
        swap += cnt
    while idx2 < mid:
        new_arr.append(arr[idx2])
        idx2 += 1
    
    # reflect
    for t in range(len(new_arr)):
        arr[start + t] = new_arr[t]
 
n = int(input())
arr = list(map(int, input().split()))
swap = 0
merge_sort(0, n)
print(swap)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다