[백준] 11279번 최대힙

⛏ 문제 파악

• 최대힙을 구하는 문제
• 시간초과 때문에 heapq을 임포트 안하고 그냥 구현하면 시간초과가 뜬다
• 파이썬 내장모듈인 heapq은 최소힙만 지원하기 때문에 최대힙으로 사용하기 위해서는 값을 음수로 변환하는 방법을 사용해야한다.
• 음수로 변환하는 것은 튜플이나 리스트를 이용하거나, 값에 * -1을 하는 방법이 있다.

👉🏻  답안

from sys import stdin
import heapq

N = int(stdin.readline())
heap = []

for i in range(N):
  x = int(stdin.readline())
  if x != 0:
    heapq.heappush(heap, [-x, x])
  elif x == 0:
    if heap:
      print(heapq.heappop(heap)[1])
    else:
      print("0")

👉🏻  또 다른 방법

import sys
import heapq
n = int(input())
heap = []
for i in range(n):
    a = int(sys.stdin.readline())
    if a == 0:
        if heap:
            print((-1)*heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap,(-1)*a)

 

📑  간단한 설명

• 본인은 리스트를 이용하여 최대힙을 구하는 방식을 활용했다.
• heapq 함수
  • heapq.heappush(heap, item) : item을 heap에 추가
  • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
  • heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

 

 

 

 

• 입력받은 값이 0인 아닌 경우, heappush(heap, [-x, x])이다.
• 입력받은 값이 0인 경우, 1) heap이 있으면 heappop[1]을 한다. 가장 작은 값이 pop되므로 -x는 가장 큰 값이 되고, return은 [1]로 양수 값이 리턴된다.
• 2) 비어있으면 0을 출력한다.