📍크리스마스 선물

문제 보러가기

💭 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

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

입력
첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)

다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

출력
a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

풀이

아이들을 만날 때마다 가장 큰 가치의 선물을 주어야 하므로, 배열 내 최대값을 제거하고 재정렬하는 로직이 반복될 것이다. 이러한 로직은 최대 힙으로 구현할 수 있다.

최대 / 최소 힙을 사용해야 하는 문제가 어떤 유형인지 슬슬 감이 잡히는 것 같다.

# 입력
# 첫 번째 줄 : 방문 횟수 n
# 다음 n줄 - 거점지 방문 : 충전한 선물의 개수와 각 선물의 가치 입력
#          아이들 만남 : 0 입력

# 출력
# 입력이 0일 때마다 아이들에게 준 선물의 가치 출력
# 선물이 없다면 - 1 출력

# 해결 방안
# 선물의 가치를 저장하는 힙 생성
# 아이들을 만날 때마다 가장 큰 가치의 선물을 주어야 하므로 최대 힙으로 구현

from heapq import heappop, heappush
from sys import stdin
input = stdin.readline

# 선물의 가치를 저장할 힙 생성
max_value = []

# 방문 횟수 입력받기
n = int(input())

for _ in range(n):
    # 입력값 a 받기
    a = input().rstrip()
    # a가 0인 경우 (문자열로 비교)
    if a == '0' :
        # 선물이 없으면 -1 출력
        if len(max_value) == 0:
            print(-1)
        # 힙에서 최소값 제거 후, 양수로 변환해서 최대값으로 출력
        else:
            print(-heappop(max_value))
    # a가 0이 아닌 경우
    else :
        # 입력받은 a를 공백으로 구분해 리스트로 저장
        values = list(map(int, a.split()))
        # 리스트의 첫 번째 값은 선물의 개수이므로 가치와 무관하니까 제거
        values.pop(0)
        # 최대 힙 구현을 위해 음수로 변환하여 max_value에 저장
        for value in values:
            heappush(max_value, -value)

새롭게 알게 된 것

heapq를 사용해서 최대 힙 구현하기

아주아주 간단하다. 파이썬 라이브러리 heapq은 최소 힙이 디폴트이다. 따라서 힙에 요소를 추가할 때 -(마이너스)를 곱해 음수로 변환해주기만 하면 최소값이 최대값이 되므로 최대 힙을 구현할 수 있다.