[백준/Python] 14235 : 크리스마스 선물

 

 

자료구조와 우선순위 큐를 사용하면 풀 수 있는 문제였다.

 

풀면서 설명이 잘 이해가 안되어서 제일 헷갈렸던 점이 있는데, 바로 예시 입출력에서 볼 수 있는 2 3 2 부분이다.

2 3 2가 모두 선물 3개라고 이해하면 위 예제의 출력이 모순적인데, 맨 앞의 숫자 2가 충전할 선물의 개수이고 바로 뒤에 따라오는 나머지 숫자들의 나열이 선물의 개수만큼 가치가 입력되어 진 것이다.

 

즉 2(개) 3(선물1의 가치) 2(선물2의 가치) 이런 셈이라고 이해하면 쉽다!

 

import sys
import heapq
N = int(input())
heap = [] 

for _ in range(N):
    data = list(map(int, sys.stdin.readline().split()))
    if data[0] == 0:
        if heap: print(-heapq.heappop(heap))
        else: print(-1)
    else:
        for present in data[1:]:
            heapq.heappush(heap, -present)

 

먼저 입력 예시가 0 이거나 숫자들의 나열 (2 3 2 4 ...) 둘 중에 하나라서 어떻게 효율적으로 입력을 받을까 고민했었는데, 그냥 일괄적으로 .split() 함수로 나눈 리스트로 저장하는 대신 sys를 사용해서 조금이라도 입력을 빠르게 처리하도록 구현하였다.

조건문에 data[0] == 0 인 경우에 pop을 하도록 구현하였는데, 이는 앞서 언급했던 점으로 0만 입력 받은 경우 data[0] 만이 존재하기 때문에 조건문으로 data[0] == 0을 사용할 수 있는 것이다.

그리고 반대로 숫자들의 나열이 입력되는 경우 맨 앞의 숫자가 선물의 개수이고 두 번째 원소부터가 선물들의 가치이므로 data[1:]만을 슬라이싱으로 추려서 차례대로 선물 가치값들을 heappush()로 힙에 삽입하도록 구현하였다.

 

참고로 이 문제 역시 최소힙 알고리즘을 최대힙으로 구현한 것이기 때문에 삽입 시에 음수 기호를 붙여서 예를 들어 3을 -3으로 삽입하여, 실제로는 최소힙이 구현된 것이지만 절댓값 상으로는 최대 힙이 구현된 형태를 만들었다.

 

그리고 이후 pop을 할 때 다시 한 번 출력 전 미리 음수 값을 붙여 출력함으로써, pop을 할 당시에는 최소값인 -3을 추출했지만 print로 출력할 때에는 음수 부호로 인해 3이 출력됨으로써 사실상 최댓값이 출력되는 구조인 것이다.