[백준/BOJ] platinum5 - 1517번 버블 소트 (Python)

▶1517 - 버블 소트

▶문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

 

▶입력

첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

 

▶출력

첫째 줄에 Swap 횟수를 출력한다.

728x90

▶풀이

버블 소트라고 해서 처음에 바로 버블 소트를 구현한 다음에 swap 할 때마다 카운트해줬다.

그랬더니 시간 초과...

 

그래서 버블 소트를 사용하지 않고 머지 소트를 사용했다.

swap 될 때 카운트를 해줬고, 정답이 나왔다.

def merge_sort(start, end):
    global count, arr

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

        a, b = start, mid + 1
        temp = []

        while a <= mid and b <= end:
            if arr[a] <= arr[b]:
                temp.append(arr[a])
                a += 1
            else:
                temp.append(arr[b])
                b += 1
                count += (mid - a + 1)

        if a <= mid:
            temp = temp + arr[a:mid + 1]
        if b <= end:
            temp = temp + arr[b:end + 1]

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


count = 0
n = int(input())
arr = list(map(int, input().split()))
merge_sort(0, n - 1)
print(count)