[백준] 11286: 절댓값 힙 - 파이썬[python]

풀이

• 절댓값을 이용해서 힙을 만들고, 같은 절댓값을 갖는 수가 여러 개일 경우 가장 작은 수를 출력하라는 문제를 보고 바로 튜플로 저장하는 방법을 떠올렸다. 최대 힙 만들 때 이용하는 코드를 봤기 때문!
• 그걸 이용해서 코드를 잘 짰는데 문제는 절댓값이 같을 때 어떻게 더 작은 수(즉 음수)를 출력하느냐였다.
  근데 코드를 짜고 제출하니까 정답이더라?
  지피티한테 물어보니까 heapq는 첫 번째 원소를 기준으로 정렬하고, 같으면 두 번째 원소로 정렬한단다. 즉, 기본이 최소 힙이니까 더 작은 애를 제거하는 것이다. 이것때문에 튜플을 쓰는 게 정답이었다!!! (얻어걸림)

코드

import sys, heapq
input = sys.stdin.readline

N = int(input())
heap = []

for _ in range(N):
    num = int(input())
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (abs(num), num))

결과