[백준] 11279번 : 최대 힙 (파이썬)

문제

나의 답안

import sys
import heapq
input=sys.stdin.readline

n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    if x==0:
        if len(arr)==0:
            print(0)
        else:
            mx=heapq.heappop(arr)[1]#튜플(-x,x)에서 x출력하기 위함(본래 최댓값)
            print(mx)
    else:
        heapq.heappush(arr,(-x,x))#우선순위 삽입(힙 정렬)|가장 큰 값을 가장 작게 만듦
        #(가장 작은 값, 실제 값) 최댓값이 루트에 올 수 있도록

접근 방법

• 우선순위 큐 문제이고, heapq를 사용해 구현해주었다.
• heapq을 사용하면 최소힙으로 구성되므로 이를 최대 값이 루트가 되는 최대힙으로 구현해주어야 한다.
• heappush를 사용해 튜플을 arr에 넣어주는데, 이때 최대힙을 구현하기 위해 튜플은 s를 음수로 만들어 (-x,x)로 구성한다.
• 최대힙으로 구현 후 조건에 따라 arr이 빈배열이 아니고 x가 0이라면 최댓값을 출력해주는데, 출력 시에는 원래 최댓값을 출력해주기 위해 힙큐의 두번째 인덱스(heapq.heappop(arr)[1])값을 출력해준다.