💡 문제
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 횟수를 출력한다
💭 접근
문제 이름은 버블 소트이지만 입력 n의 최대값이 500,000이기 때문에 O(N)의 시간복잡도를 가지는 실제 버블 소트 알고리즘을 사용하게 되면 시간초과가 발생하게 된다. 따라서 다른 정렬 방법을 사용해야 하는데, 이 문제에선 O(NlogN)의 시간복잡도를 가지는 병합 정렬을 사용하여 해결할 수 있다.
어떻게 병합 정렬을 사용하여 해결할 수 있을까?
병합 정렬은 크게 주어진 배열을 나누는 단계, 나눠진 배열을 정렬하며 합치는 단계 이렇게 두 단계로 나눠진다. 이를 미루어 보아 우리는 다시 자리를 바꾸며 합치는 단계에서 정답을 구할 수 있다.
예를 들어 7 5 9 2 라는 배열이 입력으로 주어졌다고 가정해보자.
나눠진 배열을 다시 합칠 때 만약 정렬해야하는 수가 있다면, 몇칸 이동해야 하는지 더해주는 것이다.
tmp = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
tmp.append(left[i])
i += 1
else:
tmp.append(right[j])
j += 1
ans += len(left) - i위 그림을 예로 이해해보자.
- 7과 5를 합칠 때 : 5가 7보다 작으므로 정렬 → 5 한칸 이동!
- 9와 2를 합칠 때 : 2가 9보다 작으므로 정렬 → 2 한칸 이동!
- 5, 7과 2, 9를 합칠 때 : 2가 5보다 작으므로 정렬 → 이때, 왼쪽 배열에서 5를 가리키고 있고, 오른쪽 배열에서는 2를 가리키고 있으므로
len(left) = 2, 이때i = 0따라서 → 2 두칸 이동!
📒 코드
def divide(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = divide(arr[:mid])
right = divide(arr[mid:])
return merge(left, right)
def merge(left, right):
global ans
tmp = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
tmp.append(left[i])
i += 1
else:
tmp.append(right[j])
j += 1
ans += len(left) - i
tmp.extend(left[i:])
tmp.extend(right[j:])
return tmp
n = int(input())
a = list(map(int, input().split()))
ans = 0
divide(a)
print(ans)💭 후기
각각 버블 소트, 병합 정렬 등 정렬 알고리즘을 알고는 있었지만 막상 이렇게 활용하려니 풀이법이 떠오르지 않았다... 계속해서 복습하자!
🔗 문제 출처
https://www.acmicpc.net/problem/1517
