백준 11279 풀이 (최대 힙, 우선순위 큐, heapq)

이번 문제는 힙문제이다. 문제는 간단하다 힙에 값을 넣으며 0값이 입력될때 가장 큰 값을 출력하면 된다.

단 이때 중요한 것은 힙을 만드는 것이다.

import heapq를 사용하면 일반 리스트를 힙처럼 사용할 수 있게 된다.

관련 자료는 해당 블로그에서 확인가능하다.

[파이썬] heapq 모듈 사용법

그러나 heapq를 사용하게되면 최소힙을 구현하게 된다. 따라서 최대힙과는 다른 방식이다. 그래서 블로그의 고수분은 음수값을 사용해서 우선순위를 이용하여 최대힙처럼 응용을 하셨다.

 

그래서 나도 그러한 아이디어를 베껴서 heap에 값을 저장할때 그대로 음수로 바꾸어 heap에 저장하고 꺼낼때는 양수로 바꾸어 출력하는 방식을 선택했다. 이러한 방식으로 간단하게 문제를 풀 수 있었다.

중요한것은 최소힙의 원리를 이용하여 최대힙을 구현할 수 있다는 것이다.

import sys
import heapq

n = int(input())
heap = []
for _ in range(n):
    t = int(sys.stdin.readline())
    t = -t
    if t == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(-heapq.heappop(heap))
    else:
        heapq.heappush(heap,t)