백준 문제 풀이 - 최대 힙 11279번

📜 문제 이해하기

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

💡 문제 재정의

최대힙을 구성해 최대값을 우선적으로 출력하자

✏️ 계획 수립

Python에선 기본적으로 heapq라는 모듈을 지원한다.
다만 주의할 점은 heapq의 기본형은 최소힙이므로 약간의 트릭을 사용해야 한다.
바로 튜플값을 입력하되 최대값이 가장 우선 순위를 높게 가지도록 최대값 -> 최솟값으로 바꿔주는 연산을 해야한다.
최대값이 최소값이 되는 방법은 -부호를 붙여주면된다.

💻 계획 수행

import heapq
import sys

if __name__ == '__main__':
    N = int(input())
    max_heap = []
    result = []
    for _ in range(N):
        num = int(sys.stdin.readline().rstrip())
        if num > 0:
            heapq.heappush(max_heap, (-num, num))
        else:
            if max_heap:
                result.append(heapq.heappop(max_heap)[1])
            else:
                result.append(0)

    for res in result:
        print(res)

🤔 회고

파이썬의 모듈이 있었기에 매우 빠르게 풀 수 있는 문제였다.
다음에는 직접 힙을 구현해서 문제를 풀어보아야 겠다.