|
def msort(l, start, end) :
global count
if start < end :
center = (start + end) // 2
msort(l, start, center)
msort(l, center + 1, end)
pl, pr = start, center + 1
rec = []
while pl <= center and pr <= end :
if l[pl] <= l[pr] :
rec.append(l[pl])
pl = pl + 1
else:
rec.append(l[pr])
pr = pr + 1
count = count + center + 1 - pl
if pl <= center :
rec = rec + l[pl:center + 1]
if pr <= end :
rec = rec + l[pr:end + 1]
for i in range(len(rec)) :
l[start + i] = rec[i]
n = int(input())
l = list(map(int, input().split()))
count = 0
msort(l, 0, n-1)
print(count)
|
tag : 분할 정복의 문제들을 쭉 보다가 버블 소트가 있길래 왜 있나 싶어서 본 문제
그냥 버블소트 돌리고 교환할 때마다 count를 +1하면 되지 않나? 하고 돌려봤지만 시간초과가 떴다.
결국 제목은 버블소트이지만 버블소트를 돌리지 않고 버블소트의 횟수를 구하라는 문제이다.
서로 떨어진 i번째와 j번째를 교환하는 것이, 버블 소트였다면 j-i번의 교환이었을 것이므로
다른 정렬을 돌리면서 두 원소를 교환할 때마다 count를 j-i만큼 더한다.
병합 정렬에서 이분된 왼쪽 리스트의 커서가 정렬될땐 원래 자기 자리에 들어가는 것이니 교환이 일어나지 않은 셈이고
오른쪽 리스트의 커서가 정렬될 땐 왼쪽 리스트의 길이 - 왼쪽 커서만큼의 거리를 넘어 교환되는 것이니 그만큼 count를 더하는 식으로 count를 세었다.
다른 종류의 nlogn 정렬 알고리즘에 대해서도 비슷한 카운팅이 되지 않을까 싶다. (아마도)
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 13705 Ax+Bsin(x)=C (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 3955 캔디 분배 (0) | 2021.11.17 |
| 파이썬 백준 2749 피보나치 수 3 (0) | 2021.11.17 |
| 파이썬 백준 12846 무서운 아르바이트 (0) | 2021.11.17 |
| 파이썬 백준 2696 중앙값 구하기 (0) | 2021.11.17 |