[Baekjoon 11286] 절댓값 힙 | Python

https://www.acmicpc.net/problem/11286

---

문제

 

힙에 넣고 빼는 간단한 문제인데, 힙에서 정렬 기준이 절댓값이다. 절댓값이 같다면 작은 순으로 정렬한다.

 

---

풀이

 

절댓값을 이용하기 위해 0보다 작은 경우 -1을 곱해 힙에 넣으면 원래 값을 알 수 없게 되기 때문에 절댓값을 구하여 힙에 넣는 것은 아니다.

파이썬에는 heapq(참고링크)를 통해 편리하게 힙을 사용할 수 있는데, heapq의 heappop, heappush는 단일 값 뿐 아니라 리스트도 지원한다. 리스트의 정렬 기준은 리스트의 인덱스 순이다. 따라서 절댓값과 원래값을 리스트에 담아 힙에 넣으면 절댓값 순으로 정렬되면서 원래값도 보존할 수 있다.

참고로 입력이 많으므로 sys를 사용하여 입력받아야 한다.

 

---

코드

 

import heapq
import sys
input = sys.stdin.readline

n = int(input())
heap = []
for _ in range(n):
    num = int(input())
    if num == 0:
        if len(heap) == 0:
            print(0)
        else:
            tmp = heapq.heappop(heap)
            print(tmp[1])
    else:
        if num < 0:
            tmp = [-1*num, num]
        else:
            tmp = [num, num]
        heapq.heappush(heap, tmp)