11279번: 최대 힙

문제 접근 🤔

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

힙에 원소를 추가할 때 (-num, num) 의 튜플 형대로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.

이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현되었던 heapq 모듈을 최대 힙 구현에 활용할 수 있다.

• 입력 값으로 자연수가 들어왔을 때마다 이 방식으로 heapq 를 최대 힙으로 구현한다.
• 0이 입력되었을 때, 현재 힙이 빈 상태라면 0, 아니라면 힙에 존재하는 최댓값을 출력해준다.
  
  
  

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(152 ms)

import sys
import heapq
input = sys.stdin.readline
heap = []

for _ in range(int(input())):
    num = int(input())
    if not num:
        print(heapq.heappop(heap)[1] if len(heap) else 0)
    else:
        heapq.heappush(heap, (-num, num))