BOJ 백준 14235번, 크리스마스 선물 - Python 파이썬

 

14235번: 크리스마스 선물

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

 

 

알고리즘 분류는 자료구조, 우선순위 큐 였다.

문제에서는 Max-heap 정렬을 요구했지만, 파이썬에서 제공하는 모듈인 heapq를 사용할 경우에 정렬은 min-heap 이었다.

때문에 heapq에 선물을 저장 할 때에는 양수인 우선순위를 음수로 바꿔 min-heap으로 정렬되게 하고, 꺼낼 때는 음수를 다시 양수로 변환해서 출력해줬다.

 

파이썬에서는 음수 -> 양수로 바꿀 때 그저 하이픈(-)을 앞에 붙여서 변환 가능 하지만, 아래 코드에서는 직관성을 위해 -1를 곱해줬다.

heapq.heappop(gifts) * -1  (동일)  -heapq.heappop(gifts)

 

정답 코드

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

for _ in range(n):
    a = list(map(int, input().rstrip().split()))
    if a[0] == 0:  # 아이를 만나면
        if gifts:  # 선물이 있으면
            print(heapq.heappop(gifts) * -1)  # 음수를 양수로 만들어준다.
        else:  # 선물이 없으면
            print(-1)
    else:  # 선물을 저장한다
        for i in range(a[0]):
            heapq.heappush(gifts, -a[i+1])  # 양수를 음수로 만들어서 넣어준다.

 

실패 요인: a[0] 가 선물의 개수가 아니라 그저 우선순위가 동일한 선물 인 줄 알고, 중복 요소를 삭제하는 코드를 작성했었지만 수정.