[Baekjoon 11279 / python / 실버2] 최대 힙

import heapq as hq

import sys

n = int(input())

hqq = []

for _ in range(n):

    x = int(sys.stdin.readline())

    if x >= 1:

        hq.heappush(hqq, -x)  # hq는 최소힙만 지원하기 때문에, 최대힙 처럼 사용하기 위해 음수로 저장

    else:                   # 음수로 저장하면 -가 붙으니, 가장 큰 값이 가장 위로 가게 된다

        if len(hqq) == 0:

            print(0)

        else:

            print(abs(hq.heappop(hqq)))  # 값을 꺼낼 땐 절댓값을 이용해 양수로 만든다

 

우선순위 큐가 사용된 문제다. 최대 힙으로 우선순위 큐를 구현하여 문제를 해결할 수 있다.

 

스택, 큐 문제처럼 문제 자체는 어렵지 않으나, 힙이라는 자료구조에 대한 공부가 필요할 수 있기 때문에 난이도가 비교적 높게 설정된 것으로 보인다.

 

파이썬의 heapq를 이용해 우선순위 큐를 구현할 수 있다. 다만 heapq는 "최소 힙"만 지원한다.

따라서 hq.heappush(hqq, -x) 이 부분처럼 값을 음수로 저장한다.

음수로 저장하면 가장 큰 값이 가장 작은 값이 되고, 루트 노드에 위치하게 되어 최소 힙을 최대 힙처럼 사용할 수 있게 된다.

 

이후 hq.heappop(hqq) 으로 꺼낼 땐 abs() 함수로 절댓값을 가져오게 하여, 양수로 변환시켜 사용한다.