[Python] 백준 11286 절댓값 힙

 

문제 분석

• 절댓값 힙
  1. 배열에 0이 아닌 정수 x를 넣는다.
  2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거
  3. 절댓값이 가장 작은 값이 여러개 일 때 가장 작은 수를 출력하고 그 값을 배열에서 제거
     • 이걸 확인하려면 +인지 -인지를 체크해 놓아야 한다.

 

코드 설계

• x를 힙에 넣을 때 ( 절댓값, 원래 값 )으로 넣는다.

 

정답 코드

import sys
input = sys.stdin.readline
import heapq

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

for _ in range(n) :
    x = int(input())

    if x == 0 :
        if heap :
            # print(heapq.heappop(heap))
            abs_value, x_value = heapq.heappop(heap)
            print(x_value)
        else :
            print(0)
    else :
        heapq.heappush(heap, (abs(x), x))