2022.02.11 [백준] (python 파이썬) 절댓값 힙

 

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

---

풀이

이 문제를 해결하기 위해 두개의 힙리스트를 만들었다. heap은 모든 수를 절대값으로 저장,

neg_heap은 음수 값을 절대 값으로 저장했다. 그래서 n=0일 때, neg_heap의 길이가 0이 아니고

heap[0]와 neg_heap[0]의 값이 같으면 heap의 최소값이 음수를 절대값으로 저장한 것이기 때문에 

heapq.heappop의 값에 -1을 곱해 출력하고 neg_heap의 최소 값을 제거했다.

import sys, heapq
 
heap=[]
neg_heap=[]
for _ in range(int(sys.stdin.readline())):
    n=int(sys.stdin.readline())
    if n<0:
        heapq.heappush(neg_heap,abs(n))
    if n==0:
        if len(heap)==0:
            print(0)
        else:
            if len(neg_heap)!=0 and neg_heap[0]==heap[0]:
                print(heapq.heappop(heap)*-1)
                heapq.heappop(neg_heap)
            else:
                print(heapq.heappop(heap))
 
    else:
        heapq.heappush(heap,abs(n))