BOJ 11279번: 최대 힙

www.acmicpc.net/problem/11279

11279번: 최대 힙

아이디어:

문제 이름 그대로 최대 힙을 구현하면 된다.

그런데 파이썬에서 제공하는 heapq 모듈은 최소힙이므로, 최대힙을 구현하려면 튜플을 이용하여 - 추가하는 첫번째 원소가 우선순위가 되고 이걸 기준으로 최소힙으로 정렬되므로 - 구현해야 한다. 출력할 때는 [1]번 원소를 출력하면 된다.

 

#11279번 최대 힙
import sys, heapq

N = int(sys.stdin.readline())
h = []
for _ in range(N):
    x = int(sys.stdin.readline())
    if (x==0):
        if (len(h)==0): #배열이 비어있는 경우
            print(0)
        else:
            print(heapq.heappop(h)[1])
    else:
        heapq.heappush(h,(-x,x)) #-x를 우선순위로 하여 최대힙 구현