11279 최대 힙

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

11279번: 최대 힙

 

내 풀이(최대 힙 응용 인터넷에서 참고했음)

import heapq

n = int(input())
ary = []
heap = []
rst = []
for i in range(n):
    x = int(input())
    ary.append(x)
for i in range(n):
    if ary[i] == 0:
        if heap:
            a = heapq.heappop(heap)[1]
            rst.append(a)
        else:
            rst.append(0)
    else:
        heapq.heappush(heap, (-ary[i], ary[i]))
for i in rst:
    print(i)

ary는 입력한걸 저장하고 heap은 자연수일때 숫자를 추가하는 리스트이고 rst는 0일때 최대 값을 저장하는 리스트이다. 그리고 ary[i]가 자연수일때, heap에 (-ary[i], ary[i])를 넣는다. -ary[i]는 우선순위이다. 그리고 ary[i]가 0일때, heap이 안비었으면 heapq.heappop(heap)[1]을 rst에 추가한다. 왜냐면 앞에는 우선순위라 뒤에 값만 추가한다. 그리고 heap이 비어있으면 0을 추가한다.