📩 출처
문제
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 횟수를 출력한다
👉 생각
- 문제는 버블 소트지만 버블소트로 Swap를 카운트 하면 시간초과가 발생한다.
- 따라서 병합정렬로 Swap을 카운트 하면 된다.
- split 함수는 배열의 계속 쪼개는 함수이다. 쪼갤 수 있을 때까지 쪼갠 후 merge 함수의 인자로 left와 right가 들어간다. 이때 left와 right를 비교해서 check에 작은 값을 먼저 넣어준다.
- 이따 rigth가 left보다 작은 경우에만 Swap이기때문에 카운트를 해준다.
- 그런데 left와 right가 각각 배열인 경우가 있기 때문에 i와 j를 증가시키면서 앞에서부터 값을 비교하고 cnt는 lent(left) - i 만큼 증가하게 된다.
def split(lst, n):
if n == 1:
return lst
left = lst[:n // 2]
right = lst[n // 2:]
left = split(left, len(left))
right = split(right, len(right))
return merge(left, right)
def merge(left, right):
global cnt
check = []
i = j = 0
while i < len(left) or j < len(right):
if i < len(left) and j < len(right):
if left[i] <= right[j]:
check.append(left[i])
i += 1
else:
check.append(right[j])
j += 1
cnt += len(left) - i
elif len(left) > i:
check.append(left[i])
i += 1
elif len(right) > j:
check.append(right[j])
j += 1
return check
n = int(input())
lst = list(map(int, input().split()))
cnt = 0
split(lst, n)
print(cnt)
