[백준] 11286 : 절댓값 힙 python

 

이전에 풀었던 최댓값 힙 문제에서 최대 힙을 만들기 위해 아래와 같은 방식으로 힙에 숫자를 추가했었다.

heapq.heappush(h,(-item,item))

이렇게 튜플 형식으로 값을 추가하면 튜플의 첫 번째 원소인 -item의 오름차순으로 정렬되기 때문인데,

이 문제에서는 절댓값의 오름차순으로 정렬을 해야 하니 heapq.heappush(h,(절댓값,원래값))의 형식으로 값을 추가하면 되겠다는 생각이 들었다.

 

 

1. n을 입력받는다.

2. 우선순위 큐가 될 리스트 h를 생성한다.

3. n번에 걸쳐 x를 입력받는다.

    3-1. x가 0일 때

         3-1-1. h에 아무것도 없으면 0을 출력한다.

         3-1-2. 절댓값이 가장 작은 값을 출력하고 제거한다.

    3-2. x가 0이 아니면 우선순위 큐에 (abs(x),x)) 튜플을 추가한다.

 

 

import sys
import heapq

input = sys.stdin.readline

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

for i in range(n):
    x=int(input())
    if x==0:
        if not h:
            print(0)
        else:
            print(heapq.heappop(h)[1])
    else:
        heapq.heappush(h,(abs(x),x))