(Python)[백준][우선순위큐] 크리스마스 선물

14235번: 크리스마스 선물

정답 비율: 56.582%

문제 풀이

---

우선순위큐를 이용하면 간단하게 해결할 수 있는 문제였다. 산타가 선물을 저장할 때는 우선순위 큐를 이용해 가장 가치가 높은 선물이 앞으로 오도록 하고 아이들을 만날 때 마다 큐의 가장 첫 요소를 꺼내어 준다.

우선순위큐는 가장 낮은 값부터 pop되기 때문에 저장을 할 때는 -를 붙이고 꺼낼 때 다시 -를 붙여줌으로써 큰 숫자가 가장 앞에 오도록 하고 가장 먼저 꺼낼 수 있도록 할 수 있다.

소스 코드

import heapq 
import sys
input = sys.stdin.readline

n = int(input())
gifts = []

for i in range(n):
    a = list(map(int, input().split()))
    if a[0]==0:
        if len(gifts)==0:
            print(-1)
        else:
            tmp = -heapq.heappop(gifts)
            print(tmp)
    else:
        for j in range(a[0]):
            heapq.heappush(gifts, -a[j+1])