11286- 절댓값 힙

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

11286번: 절댓값 힙

 

min-heap을 이용해 해결하면 된다. 절댓값이 작은 순서대로 정렬 되어야 하고 같은 값이 두개 이상이라면 이 중에서 원래 값이 더 작은(= 음수) 값을 먼저 출력해야 하므로 heapq의 min-heap에 (절댓값, 원래값)의 튜플 형태로 원소를 넣어 주면 퓨플의 순서대로 정렬을 할 수 있다.

 

 

import sys
import heapq
input = sys.stdin.readline
N = int(input())
pq = []
for _ in range(N):
    x = int(input())
    if x == 0:
        print(heapq.heappop(pq)[1] if pq else 0)
    else:
        heapq.heappush(pq, (abs(x), x))

heapq를 import하여 문제를 해결했다. heapq의 설명은 다음 글 참조.

2022.04.22 - [ALGORITHM/Data Structure] - [Python] min-hip을 이용한 Priority Queue

[Python] min-hip을 이용한 Priority Queue