백준 11286 절댓값 힙

 

import heapq, sys

input = sys.stdin.readline

min_heap = []
max_heap = []

for _ in range(int(input())) :
    
    num = int(input())
    
    if num > 0 :
        heapq.heappush(min_heap, num)
    elif num < 0 :
        heapq.heappush(max_heap, -num)
    else :
        if len(min_heap) == 0 :
            if len(max_heap) == 0 :
                print(0)
            else :
                print(-heapq.heappop(max_heap))
        elif len(max_heap) == 0 or min_heap[0] < max_heap[0] :
            print(heapq.heappop(min_heap))
        elif min_heap[0] >= max_heap[0] :
            print(-heapq.heappop(max_heap))

 

최소힙과 최대힙을 이용해서 문제를 해결했다.

 

파이썬의 힙은 최소힙으로 작동하기 때문에 하나는 음수를 담당하는 힙, 하나는 양수를 담당하는 힙으로 구성했다.

 

양수일경우 최소힙에, 음수일 경우 최대힙에 추가하고 0일 경우 조건에 따라 출력할 수를 정했다.

 

둘다 비었을 경우 0을 출력하고, 하나만 빈 경우는 다른 힙의 값을 출력한다.

 

그리고 둘다 비지 않은 경우에는 둘 중 작은 값을 출력한다.