BOJ 1715: 카드 정렬하기 [Python 3]

 

---

Heap이란?

최소 힙의 예시이다.

위에 있는 부모 노드보다 밑에 있는 자식 노드가 더 큰 노드이다.

맨 위에 있는 수를 제외하고는 자식이 부모보다 큰 조건을 만족 시키면서, random하게 sort 되어 있는 모습이다.

그렇기에 '반정렬' 상태라고 명한다.

최대 힙은 부모보다 자녀의 크기 작은 경우이다.

heapq 라는 module을 통해 구현할 수 있고, 일반적인 배열 형태로 heap을 구현하기에 단순한 list에 heapq의 함수들을 사용하면 heap으로 이용할 수 있다.

---

코드

import sys
import heapq
input=sys.stdin.readline
n=int(input())
data=[int(input()) for _ in range(n)]
heapq.heapify(data)
answer=0
while len(data)!=1:
    number=0
    for i in range(2):
        number+=heapq.heappop(data)
    answer+=number
    heapq.heappush(data,number)
print(answer)

heap에 모든 input들을 넣고,

부모 노드르르 두번 pop 한다. 그 이후 그 합을 다시 heap에 push한다.