문제풀이

[백준] 11279 최대 힙

자르비옹스 2022. 1. 16. 18:46

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

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

파이썬에서 제공하는 heapq는 기본적으로 최소 힙이다. 그래서 이를 활용하여 최대 힙을 구현할 경우, 힙에 push하는 값에 -1을 곱하여 음수로 추가하면 된다. 물론 출력할 때에도 -1을 곱하여 원래 값으로 되돌려야 한다.

 

풀이

import heapq

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