[CLASS 3]백준 11286번 - 절댓값 힙

11286번 : 절댓값 힙

 

직접 구현하지는 않고 힙큐 모듈을 사용했다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
import heapq
input = stdin.readline

plusHeap = []
minusHeap = []
for _ in range(int(input())):
    req = int(input())
    if req:
        if req > 0:
            heapq.heappush(plusHeap,req)
        else:
            heapq.heappush(minusHeap,-req)
    else:
        if not plusHeap and not minusHeap:
            print(0)
        elif not plusHeap:
            print(-heapq.heappop(minusHeap))
        elif not minusHeap:
            print(heapq.heappop(plusHeap))
        else:
            p = heapq.heappop(plusHeap)
            m = heapq.heappop(minusHeap)

            if m <= p:
                print(-m)
                heapq.heappush(plusHeap,p)
            else:
                print(p)
                heapq.heappush(minusHeap,m)

 

양수를 입력받았을때 저장할 큐와 음수를 입력받았을 때 저장할 큐를 달리했다. 이때 음수의 경우 양수로 바꾸어 큐에 저장하면 된다. 그리고 출력할 때는 두 큐에서 수를 하나씩 pop한 뒤 음수를 입력받았을때 넣어준 큐에서 pop한 값(지금은 양수)이 더 작거나 같다면 이를 다시 음수로 바꾸어 출력하면 된다. 반대의 경우도 같다. 물론 출력하지 않은 수는 다시 큐에 집어넣어야 한다.