[실버 2] 백준 11279 - 최대 힙 (파이썬)

분류 : 자료구조

링크 : https://www.acmicpc.net/problem/11279

풀이

백준 1927과 비슷한 문제이다. 1927 최소 힙 문제에서는 정석대로 heap에 값을 양수로 넣었지만, 이번 문제는 최대 힙을 구하는 문제이기에, -를 붙여서 음수로 넣어주면 힙에서는 최대 힙으로 정렬되게 된다.

이때 문제점은 pop 할때도 음수로 나오기에, 다시한번 -를 붙여주면, 최대 힙으로 출력 할 수 있다.

코드

# 백준 11729 - 최대 힙

import heapq
import sys

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

for i in range(N) :
    x = int(input())
    if x == 0 :
        if len(heap) > 0 :
            print(-heapq.heappop(heap))
        else :
            print(0)
    else :
        heapq.heappush(heap, -x)