백준 알고리즘 파이썬(Python) 11279번 최대 힙

---

 파이썬의 heapq(힙 큐) 내장 모듈을 사용하여 푸는 문제이다.

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다.

이진트리 기반의 최소 힙을 그림으로 쉽게 나타내면 다음과 같다.

 

heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다. 첫 번째 인자는 원소를 추가할 대상 리스트이며 두 번째 인자는 추가할 원소를 넘긴다.

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)

#출력값 -> [1, 3, 7, 4]

 

heapq 모듈의 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있다. 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴한다.

 

print(heapq.heappop(heap))
print(heap)

#출력값 
#  3
#  [4, 7]

 

하지만 이 문제는 최소 힙이 아닌 최대 힙을 구하는 문제이다. 따라서 약간의 요령이 필요하다.

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (-num)) #heapq는 min heap만을 지원하므로 -를 통해 뒤집어 준다.
    else:
        try:
            print(-1 * heapq.heappop(heap))
        except:
            print(0)

입력받은 num을 heapq에 추가 해줄 때 num에 ' - '를 붙임으로써 가장 큰 수를 가장 작은 수로 만들어준다.

그리고 heappop을 통해 최소 힙을 뽑아 주면서 거기에 다시 -1을 곱해주어 다시 최댓값으로 만들어 주면 된다.