백준 11286번: 절댓값 힙

문제

문제바로가기> 백준 11286번: 절댓값 힙

풀이 1

두개의 tuple(절댓 값, 기존 값)을 heap에 집어 넣어, 출력할 때 index를 참조해 출력하는 방식으로 풀 수 있다.

import sys
import heapq

input = sys.stdin.readline
heap = []

for i in range(int(input())):
    x = int(input())
    if x:
        if(x>0): heapq.heappush(heap, (x, x))
        else: heapq.heappush(heap, (-x, x))
    else:
        if len(heap): print(heapq.heappop(heap)[1])
        else: print(0)

풀이 2

양수와 음수를 저장하는 두가지 heap을 사용하는 방식으로도 풀 수 있다.
풀이 1보다 메모리와 시간 두 측면 모두에서 더 나았다.

import sys
import heapq

input = sys.stdin.readline
pos_heap = []
neg_heap = []

for i in range(int(input())):
    x = int(input())
    if x:
        if(x>0): heapq.heappush(pos_heap, x)
        else: heapq.heappush(neg_heap, -x)
    else:
        if len(pos_heap) and len(neg_heap):
            if abs(pos_heap[0])>=abs(neg_heap[0]): print(-heapq.heappop(neg_heap))
            else: print(heapq.heappop(pos_heap))
        elif len(neg_heap):
            print(-heapq.heappop(neg_heap))
        elif len(pos_heap):
            print(heapq.heappop(pos_heap))
        else: print(0)