[Python] 절댓값 힙 - 백준

해당 글은 백준 11286번 문제 '절댓값 힙'을 다룬다.

문제

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

11286번: 절댓값 힙

 

설명

해당 문제는 heapq 라이브러리를 사용해서 해결할 수 있다.

기본으로 최소 힙으로 되어있으므로, 절댓값 x와 기본 x를 같이 튜플 타입으로 넣어주고

정렬이 되는 기본값은 튜블의 인덱스 0번째 값이므로 해당 값을 pop 하고, 기본 x를 출력시에만 넘겨주면 된다.

그리고 sys 라이브러리의 input을 sys.stdin.readline으로 정의해서 사용해야 시간초과가 뜨지않는다.

 

코드

import heapq, sys
input = sys.stdin.readline
n = int(input())
queue = []
for i in range(n):
    x = int(input())

    if x == 0:
        if len(queue) == 0:
            print(0)
        else:
            abs_tx, tx = heapq.heappop(queue)
            print(tx)
    else:
        heapq.heappush(queue, (abs(x), x))