절대값 힙(백준 11286번)

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

나의 풀이

from heapq import heappop,heappush
import sys

N=int(input())
abs_heap=[]

for _ in range(N):
    I=int(sys.stdin.readline().strip())
    if I==0:
        if abs_heap:
            min_abs=heappop(abs_heap)
            tmp_list=[]
            tmp_list.append(min_abs)
            while abs_heap and min_abs[0]==abs_heap[0][0]:
                tmp_list.append(heappop(abs_heap))
            tmp_list.sort(key=lambda x:x[1],reverse=True)
            print(tmp_list.pop()[1])
            for tmp in tmp_list:
                heappush(abs_heap,tmp)
        else:
            print(0)
    else:
        heappush(abs_heap,(abs(I),I))

• heap이 절대값 기준으로 정렬되도록 하기 위해 (절대값, 원소)의 tuple형태를 heap에 넣어주었다.

• 절대값이 같은 모든 값들을 heap에서 빼주었고, 그 값들로 이루어진 list를 tuple[1], 즉 원래의 값 기준으로 정렬한 이후, 가장 작은 값을 출력하고 나머지는 다시 heap에 넣어주었다.

  주의) heap에 원소가 없을 때, heappop()을 하면 오류가 발생한다.