백준 11286: 절댓값 힙 (파이썬 풀이)

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

11286번: 절댓값 힙

 

이 문제는 절댓값을 비교해서 가장 작은 값을 꺼내야 하므로, 우선순위 큐에 절댓값을 저장해야 합니다.

 

하지만 절댓값이 같은 수가 여러개 있을 경우 그중에 작은값(양수와 음수가 있다면 음수)을 골라야하므로

원래 원본 값도 같이 저장해야 합니다.

 

따라서 우선순위큐에 튜플을 이용하여 (절댓값, 원본값)을 우선순위큐에 넣어줍니다.

우선순위큐는 선형 자료구조일 경우 기본적으로 맨 앞의 요소부터 정렬하여 넣습니다.

(cf. 문자열도 가능한데 문자열은 사전순으로 'a' < 'b' 입니다.)

 

import sys
input = sys.stdin.readline

import heapq

hq = []
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        print(heapq.heappop(hq)[1] if len(hq) else 0)
    else:
        heapq.heappush(hq, (abs(x), x))

x가 0일 경우 hq가 존재하면 heappop 하여 원본값 (1번 인덱스)를 꺼내고,

hq 길이가 0이면 0을 출력

 

0이 아닐 경우 heappush 하는데 (절댓값, 원본값)을 튜플로 push 하면 됩니다.