BOJ 11286: 절댓값 힙 [Python 3]

이번 문제는 기본 자료구조 중 하나인 힙을 이용하는 문제였다.

BOJ 11286: 절댓값 힙

이 문제의 경우에는, 문제를 푸는 것은 쉽지만, 제한된 시간 내에서 푸는 것이 어려운 점이다. 최대한 시간을 줄여야 한다.

 

from heapq import *
import sys
input=sys.stdin.readline
n=int(input())
heap=[]
for _ in range(n):
    n=int(input())
    if n==0:
        if not heap:
            print(0)
        else:
            print(heappop(heap)[1])
    else:
        heappush(heap,(abs(n),n))

heapq를 import 하고, heap에 push할 때 수의 절댓값과 실제값을 tuple에 넣어서 저장한다.

이렇게 되면, tuple의 첫째 자리가 index로 heapify되기 때문에 문제 없이 sort할 수 있다.

pop할 때는 실제 값인 tuple의 1번째 index를 print해준다.