[백준] 11286 - 절대값 힙

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

11286번: 절댓값 힙

문제 한줄 이해

-배열에 정수를 넣은 다음 꺼낼때 절대값이 작은 수가 먼저 출력되고 절대값이 같은 경우에는 그 중 작은 값을 꺼내는 절대값 힙 구현하기

생각난 풀이

1번째 방법: 기본적으로 우선순위 큐를 사용 하려했고 기본적으로 파이썬에서 제공하는 heapq는 최소힙으로 제일 작은 값부터 출력이 된다.

이때 나는 힙에 넣어줄때 +라면(x의 절대값, 2), -라면(x의 절대값,1)을 넣으려 했다. 이유는 첫번째 요소가 같다면 두번째 요소를 비교해 작은 값을 먼저 출력해주기 때문이다.

import sys
import heapq
n = int(sys.stdin.readline())
hq = []

for i in range(n):
    x = int(sys.stdin.readline())
    
    if x > 0:
        heapq.heappush(hq,(x,2))
    elif x< 0:
        heapq.heappush(hq,(abs(x),1))
    else:
        if hq:
            a,b = heapq.heappop(hq)
            # b가 1이라면 원래의 x값은 음수
            if b == 1:
                print(-a)
            # b가 2라면 원래의 x 값은 양수
            else:
                print(a)
        else:
            print(0)