[백준 1517] 버블 소트(merge sort로 풀기)

문제 출처 : https://www.acmicpc.net/problem/1517

1517번: 버블 소트

이 문제의 이름은 버블 소트이지만 버블 소트로 문제를 풀려고 한다면 시간초과로 문제를 해결할 수 없습니다. 이 문제는 앞에서 배운 Inversion Counting 으로 해결할 수 있습니다. 앞에서 세그먼트 트리로 푸는 방법을 배웠다면 이번에는 merge sort를 사용하여 문제를 풀어보도록 하겠습니다.

세그먼트 트리의 문제점

세그먼트 트리로 풀 수 있지만 머지 소트로 푸는 방법을 배우는 이유는 다음과 같습니다.

1. 좌표 압축을 통해 모든 정점의 좌표값을 바꿔주는 과정이 필요합니다.
2. 파이썬 속도 문제로 탑 다운 세그먼트 트리 형태로 문제를 해결하면 시간초과가 됩니다. 바텀업 세그먼트 트리를 이용하여 문제를 해결해야 합니다.

좌표 압축을 하고, 바텀업 세그먼트 트리로 문제를 바꾸는 복잡한 과정들을 거치기 보다는 mege sort로 쉽게 해결하는 코드를 작성해 보겠습니다. 문제를 푸는 아이디어는 Inversion Counting의 세그먼트 트리와 같습니다. 리스트의 값을 merge sort를 하기위해 모든 원소들을 쪼개어 줍니다. 그리고 다시 합치면서 역순의 개수를 세는 것입니다.

입력 받기

N = int(input())
arr = list(map(int, input().split()))

cnt = 0
merge_sort(0, N - 1)
print(cnt)

원소의 수 N과 수열 arr을 입력 받습니다. cnt값은 버블 소트의 반복 횟수를 저장해 놓는 변수 입니다. merge_sort 함수에서 global로 사용할 예정 입니다. 모든 작업이 끝난 후 cnt 값을 출력해주면 됩니다.

divide 단계

def merge_sort(start, end):
    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)

        merge(start, end)

merge sort는 모든 원소들을 하나하나 나누는 divide 단계와 모든 원소들을 다시 합쳐주는 merge단계가 있습니다.

merge_sort 라는 함수를 통해 재귀로 반복해 줍니다. 다음으로 리스트를 다시 합쳐주는 merge 단계에서 우리가 구해야하는 역순의 쌍의 개수를 찾습니다.

merge 단계

def merge(start, end):
    global cnt
    mid = (start + end) // 2
    i, j = start, mid + 1
    new_arr = []

    while i <= mid and j <= end:
        if arr[i] <= arr[j]:
            new_arr.append(arr[i])
            i += 1
        else:
            new_arr.append(arr[j])
            j += 1
            cnt += mid + 1 - i 

    if i <= mid:
        new_arr += arr[i : mid + 1]
    
    if j <= end:
        new_arr += arr[j : end + 1]

    for i in range(len(new_arr)):
        arr[start + i] = new_arr[i]

cnt값이 역순의 쌍의 숫자입니다. 여러 곳에서 쉽게 사용할 수 있도록 이 값을 global로 선언해 주었습니다. 다음으로 merge_sort는 왼쪽동을 담당하는 left와 오른쪽을 담당하는 right를 가지고 새로운 리스트를 만들어 줍니다. 이 때 i 번째 값과 j 번째 값이 순서대로 되어있지 않다면 역순으로 되어 있다는 뜻이 됩니다. 우리가 구하려는 역순의 개수이기 때문에 cnt 값에 추가로 넣어줍니다. 이렇게 구한 cnt 값을 출력해주면 문제를 해결할 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())
arr = list(map(int, input().split()))

def merge(start, end):
    global cnt
    mid = (start + end) // 2
    i, j = start, mid + 1
    new_arr = []

    while i <= mid and j <= end:
        if arr[i] <= arr[j]:
            new_arr.append(arr[i])
            i += 1
        else:
            new_arr.append(arr[j])
            j += 1
            cnt += mid + 1 - i 

    if i <= mid:
        new_arr += arr[i : mid + 1]
    
    if j <= end:
        new_arr += arr[j : end + 1]

    for i in range(len(new_arr)):
        arr[start + i] = new_arr[i]

def merge_sort(start, end):
    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)

        merge(start, end)        
cnt = 0
merge_sort(0, N - 1)
print(cnt)