Python - [백준]1517-버블 소트

출처

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

문제

버블소트 수행 시 SWAP이 몇번 일어났는지 세는 문제이다.

접근 방법

처음에 그냥 곧이 곧대로 버블소트를 사용하여 몇번 스왑했는지 구하는 작성하고 너무 쉽다고 생각하고 있을 찰나 시간초과에 걸렸다.

찾아보니 이 문제는 병합정렬을 통해 접근해야 시간초과가 발생하지 않는다고 한다. 잘 생각해보니 병합정렬을 할때 몇개를 바꾸었는지 셀 수 있고 나름 접근방법도 비슷했다. 그래서 병합정렬을 구현하고 몇개를 바꾸었는지 세도록 구현하였다.

start, end, mid의 원리가 이해가 잘 안된다면 직접 아래코드에 프린트를 넣어 지켜보면 이해가 더 잘 된다.

병합정렬이 무엇인지는 인터넷을 참고하면 더 좋을 것 같다.

Merge Sort - 대표적인 Devide and Conquer 알고리즘

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
answer = 0
def merge_sort(start, end):
    global answer, arr
    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)
        temp = []
        x, y = start, mid + 1
        while x <= mid and y <= end:
            if arr[x] <= arr[y]:
                temp.append(arr[x])
                x += 1
            else:
                temp.append(arr[y])
                y += 1
                answer += (mid - x) + 1
        if x <= mid:
            temp = temp + arr[x:mid + 1]
        if y <= end:
            temp = temp + arr[y:end + 1]
        for i in range(len(temp)):
            arr[start+i] = temp[i]
        
    

merge_sort(0, n-1)
print(answer)