백준 11279번: 최대 힙

백준 11279번: 최대 힙

아이디어

파이썬 heapq 모듈은 이진 트리 기반의 최소 힙 자료구조를 제공한다. 가장 작은 값이 항상 트리의 루트에 위치한다. 최대 힙 자료구조는 제공하지 않기 때문에 잡기술을 사용해서 최대 힙으로 만들어야 한다. 어떤 잡기술이냐면.. push할 때 -를 붙이고 pop할 때 다시 -를 붙여서 원래대로 돌리는 잡기술이다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())

maxHeap = []

for i in range(N):
    num = int(input())
    if num != 0:
        heapq.heappush(maxHeap, -num)
    else:
        if not maxHeap:
            print(0)
        else:
            print(-heapq.heappop(maxHeap))

여담

작년 1학기때 열심히 자료구조를 들으며 C언어로 최대, 최소 힙을 구현했던 기억이 있다. 나중에 시간나면 자료구조 복습을 해야겠다. 22년 인생 중 가장 코딩을 열심히 했던 순간이다.