184. 11286(절댓값 힙) - 파이썬

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
que = PriorityQueue(maxsize=N)
result = []

for _ in range(N):
    X = int(input())

    if(X == 0):
        if que.empty():
            result.append("0")
        else:
            tmp = que.get()
            if tmp[1] < 0:
                result.append(str(-tmp[0]))
            else:
                result.append(str(tmp[0]))

    else:
        if X > 0:
            que.put([X, 1])
        else:
            que.put([-X, -1])

print("\n".join(result))

문제요약

값을 입력하는데 0이면 현재 입력된 값 중에 절대값 기준 가장 작은 값을 출력하라.(절대값이 같다면 더 작은 값 출력)

설명

이 문제는 굳이 우선순위 큐가 아닌 힙을 이용하여 (어차피 힙도 우선순위 큐) 풀 수 있다.

import sys
import heapq

n = int(sys.stdin.readline())
h = []

for _ in range(n):
    data = int(sys.stdin.readline())
    if data != 0:
        heapq.heappush(h,(abs(data),data))
    else:
        if not h:
            print(0)
        else:
            print(heapq.heappop(h)[1])

하지만 지금까지 PriorityQueue를 사용했기 때문에 이 문제에서도 우선순위 큐를 사용했다.

 

    else:
        if X > 0:
            que.put([X, 1])
        else:
            que.put([-X, -1])

먼저 que에 입력 되는 부분을 보자.

 

만약 X입력값이 음수라면 -를 붙이고 음수라는 것을 알리기 위해 배열 1에 [-1]을 붙여준다.

양수는 음수와 반대로 진행한다.

 

그러면 입력값을 양수로 기준으로 하여 값을 집어 넣을 것이다.

    if(X == 0):
        if que.empty():
            result.append("0")
        else:
            tmp = que.get()
            if tmp[1] < 0:
                result.append(str(-tmp[0]))
            else:
                result.append(str(tmp[0]))

0이 들어오면 result에 값을 추가하는데 큐가 비어있을 경우 전에 하던대로 진행하면 되고, 입력을 할 때가 문제이다.

 

먼저 tmp에 리스트를 저장한다.

tmp[1]이 음수냐 양수냐에 따라서 result에 -를 붙여줄지 안 붙여 줄지를 결정한다.

tmp[1]이 음수라는 것은 그 수는 본래 음수 였다는 것을 말하는 것이므로 result에 넣을 때 -를 붙여 본래의 값으로 만들어 준다.