백준[Python] - 11279:최대 힙

문제

예제

• 입력
  13
  0
  1
  2
  0
  0
  3
  2
  1
  0
  0
  0
  0
  0
• 출력
  0
  2
  1
  3
  2
  1
  0
  0

풀이

최대 힙을 사용하면 간단하게 해결 가능하다.

최대 힙

• 힙이란?
  • 참고 : [https://sdsf1225.tistory.com/59]

'최대힙'은 파이썬의 heapq 라이브러리를 응용하면 간단하게 사용 가능하다.

 

heapq 라이브러리는 기본적으로 '최소 힙'을 제공하기 때문에 이를 이용해 힙에 넣고자 하는 수의 반대 부호를 넣어주면 최대 힙이 구현 가능하다.

# 최대 힙
import sys, heapq
input = sys.stdin.readline
n = int(input().strip())
heap = []
for _ in range(n):
    num = int(input().strip())
    if num==0:
        if heap:
            _pop = heapq.heappop(heap)
            print(_pop[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (-num,num))