[백준] 14235 크리스마스 선물 (Python 파이썬)

문제 설명

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

14235번: 크리스마스 선물

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다.

올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다.

하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다.

또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

이제 산타가 선물을 나눠줄 것이다.

차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

---

풀이 과정

우선순위큐를 이용하면 간단하게 해결할 수 있는 문제였다.

산타가 선물을 저장할 때는 우선순위 큐를 이용해 가장 가치가 높은 선물이 앞으로 오도록 하고

아이들을 만날 때 마다 큐의 가장 첫 요소를 꺼내어 주면 된다.

 

우선순위큐는 숫자가 낮은 값부터 저장이 되기 때문에

저장을 할 때는 -를 붙이고 꺼낼 때 다시 -를 붙여줌으로써

큰 숫자가 가장 앞에 오도록 하고 가장 먼저 꺼낼 수 있도록 할 수 있다.

import heapq

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

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

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !