[Algorithm] 백준 11279 : 최대 힙

문제
https://www.acmicpc.net/problem/11279
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/11279.%E2%80%85%EC%B5%9C%EB%8C%80%E2%80%85%ED%9E%99/%EC%B5%9C%EB%8C%80%E2%80%85%ED%9E%99.py

비슷한 유형인 백준 1927 최소 힙과 같이 최대 힙 뼈대 문제였다. 최소 힙 문제에서도 heapq 라이브러리를 사용해서 풀어주었는데, 이 문제도 간단한 트릭을 사용하여 최대힙으로 구현할 수 있었다.

heapq.heappush(heap, (-i, i))를 통해 (-i, i) 튜플을 heap 리스트에 넣어주었다. 이렇게 하면 가장 큰 값에 -가 붙어서 가장 작은 값으로 변환되고, heapq는 최소힙을 기본으로 하기 때문에 -(가장 큰 값)이 루트에 위치하게 된다.

힙에서 값을 pop 하여 사용할 때는 원래의 값을 사용하기 위해 heapq.heappop(heap)[1]을 사용하면 (-i, i) 튜플 중 원래 값인 i를 사용할 수 있게 된다.

< 풀이 코드 >

import sys
import heapq 

input = sys.stdin.readline

N = int(input())
heap = []

for _ in range(N):
  i = int(input())

  if i == 0:
    if len(heap) == 0:
      print(0)
    else:      
      print(heapq.heappop(heap)[1])  
  else:
    heapq.heappush(heap, (-i,i))