#291 백준 파이썬 [2220] 힙 정렬

https://www.acmicpc.net/problem/2220

 

SOLUTION

가장 많은 스왑을 하게 되는 힙 정렬 순서는 어떻게 될까?

노트에 10까지 써보니 n 힙 정렬에서 n을 삭제하면 n-1 힙 정렬과 동일해진다는 것을 알게 되었다.

즉 이전 리스트를 받아 최댓값을 대입했을 때 가장 많은 스왑을 가져가면 되는 것이다.

n번 째에 가장 많은 스왑을 일으키기 위해서는 n이 가장 하단 레벨의 1 옆으로 가야한다.

해당 max heap에서 7이 추가 될 경우 1은 오른쪽 맨 아래로 이동하게 되고 기존의 1자리에는 7이 위치하게 된다.

7이 가장 상단에 올라가기 위해 은 7은 3과 스왑, 다시 7은 6과 스왑되며 2번의 스왑을 일으키게 된다.

 

이를 해결하기 위해서 Bottom Up방식을 이용했다.

 

1) n-1 힙 뒤에 최댓값 n을 추가해준다.

2) n-1 힙의 맨 뒤 숫자인 1과 바꾼다.

3) j//2에 위치한 부모 노드로 최댓 값을 올려보낸다.(스위치한다.)

4) n-1위치에서 1의 위치로 최댓값이 갈 때 까지 3)을 반복한다.

PYTHON CODE

n = int(input())
heap = [0, 1]

def swap(arr, x, y): #두 위치를 바꾸는 코드
    temp = arr[x]
    arr[x] = arr[y]
    arr[y] = temp
 
for i in range(2, n+1):
    heap.append(i) #맨 뒤에 최댓값 추가
    swap(heap, i, i-1) #1과 바꿔줌
    j = i-1 #j위치에 있는 최댓값
    while j != 1: #j위치에 있는 최댓값은 최상단에 위치할 때 까지 부모 노드와 지속적으로 바꾸어줌
        swap(heap, j, j//2) #교환
        j = j//2 #부모 노드의 위치

for i in heap[1:]:
    print(i, end = ' ')