[파이썬, Python] 백준 11279: 최대 힙

문제

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

11279번: 최대 힙

코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
arr = list()

for i in range(n):
    x = int(input())
    if x == 0:
        if not arr:
            print("0")
        else:
            print(-heapq.heappop(arr))
    else:
        heapq.heappush(arr, -x)

설명

heapq를 통해 힙을 구현해서 풀이했다.

heapq의 경우 최소 힙은 지원하지만 최대 힙은 지원하지 않는데,
응용하여 최대 힙을 사용할 수 있다.

우선 힙에 넣을 때,
음수로 만들어서 넣어준다.

이렇게 한다면 가장 큰 수가 최소 값이 되고,
(x의 범위가 자연수이므로 음수는 고려 X)
heappop을 통해 최소 값을 출력하면 -x가 나오게 되는데,
이를 -를 한번 더 곱해주어 출력하면 최대 힙으로 사용이 가능하다.