1. 문제 설명
[문제 내용]
크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.
이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.
[입력]
첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)
다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)
[출력]
a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.
[입출력 예]
2. 풀이
import heapq
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0]) # 방문 횟수
max_heap = [] # 최대 힙을 사용
index = 1 # 현재 읽을 데이터의 위치
for _ in range(n):
a = int(data[index])
index += 1
if a > 0:
for _ in range(a):
gift_value = int(data[index])
index += 1
heapq.heappush(max_heap, -gift_value)
else:
if not max_heap:
print(-1)
else :
print(-heapq.heappop(max_heap))3. 회고
3-1. 문제 해결 과정
문제 자체를 이해하지 못해서 포기했던 문제인데, 입출력 예시에서 2 3 2가 무엇을 의미하는지 파악하는 것이 어려웠었다. 알고보니 맨 앞의 2는 선물의 개수이고 뒤의 3과 2는 선물의 가치였다. 나중에 보니까 쉽게 느껴지는데 왜 어렵게 느꼈는지 살짝 의문이 든다.
방문 횟수를 data의 맨 앞 인덱스에 저장한 다음, 우리는 값이 큰 선물을 아이들에게 먼저 준다고 했으니 최대 힙을 구현한다. 선물의 개수에 따라 값을 받아온 다음 음수로 바꾸어서 최대 힙에 저장한다.
다만 아이에게 선물을 줄 때는 다시 양수로 바꾸어서 힙에서 삭제하는 것이 포인트이다. 이는 파이썬에서 최소 힙만 지원하기 때문임을 잊지 말아야 한다.
3-2. 새롭게 배운 내용
- 최대 힙(Max Heap) : 부모 노드의 값이 항상 자식 노드보다 크거나 같다
9
/ \
7 6
/ \
3 5- 최소 힙(Min Heap) : 부모 노드의 값이 항상 자식 노드보다 작거나 같다
2
/ \
3 5
/ \
7 8가장 큰 값을 찾고자 할 때는 음수로 변환하여 저장한 다음 -heappop()을 통해 처리한다. (최대 힙 이용) 반대로 가장 작은 값을 찾고자 할 때는 heappop()을 통해 처리한다.
