[BaekJoon] 1517 버블 소트 (Platinum 5) - Python

문제

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 횟수를 출력한다

 

입력예시1)

3
3 2 1

출력예시1)

3

 

---

코드

import sys
input = sys.stdin.readline

N = int(input()) # 숫자의 개수 입력
num = list(map(int, input().rstrip().split())) # 숫자 입력
result = 0 # 결과값 저장할 변수 생성

def Sort(start, end): # 병합정렬

    global result, num

    if start < end:

        mid = (start + end) // 2
        Sort(start, mid)
        Sort(mid + 1, end)

        a = start
        b = mid + 1
        buf = []

        while a <= mid and b <= end:
            if num[a] <= num[b]:
                buf.append(num[a])
                a += 1
            else:
                buf.append(num[b])
                b += 1
                result += (mid - a + 1) # 여기
                # 왼쪽과 오른쪽의 리스트를 비교했을 떄, 만약 오른쪽이 왼쪽보다 작다면?
                # 왼쪽의 남은 확인하지 않은 인덱스들은 오른쪽보다는 무조건 큰 값들이 있는 것 이기 때문에
                # 왼쪽 리스트의 개수만큼 더해준다.
        
        if a <= mid: buf = buf + num[a:mid + 1]
        if b <= end: buf = buf + num[b:end + 1]
        
        for i in range(len(buf)): num[start + i] = buf[i]

Sort(0, N - 1) # 병합정렬 실행
print(result) # 결과값 출력

---

실행 화면

 

---

채점 결과