[백준 / python] 11286번: 절댓값 힙

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

11286번: 절댓값 힙

 

문제분석

정수를 입력 받고 이를 배열에 저장받은 다음 0을 입력 받았을 때, 배열에서 절댓값이 가장 작은 값을 pop 하면 되는 문제이다. 단, 0을 입력받았을 때, 배열에 아무것도 없을 경우에는 그냥 0을 출력해야 한다. 입력 되는 정수는 절댓값이 2^31보다 보다 작으며 N은 1보다 크고 100000보다 작은 자연수이다. 또한, 절댓값이 같은 경우 더 작은 값을 출력한다. 즉, N만큼 loop문을 돌면서 입력을 받고 그에 따른 동작을 하면 되는 문제이며 절댓값이 같은 경우 음수를 먼저 pop하면 되는 문제이다.

 

코드

from queue import PriorityQueue as pq
from math import pow

input = __import__('sys').stdin.readline

min_h = pq()
n = int(input())

for _ in range(n):
    min_h.put((pow(2, 31), 0))
    x = int(input())
    if x == 0:
        print(min_h.get()[1])
        continue
    if x < 0:
        min_h.put((abs(x)-0.1, x))
    else:
        min_h.put((abs(x), x))

 

문제풀이

우선순위 큐를 이용하면 풀 수 있는 문제이다. 우선순위 큐는 들어가는 우선순위가 낮을수록 먼저 빠져나오게 작동하기 때문에 입력 받은 값의 절댓값을 우선순위로 지정해주면 자동적으로 get()을 했을 때, 절댓값이 낮은 값이 pop하게 된다. 또한, 0을 입력 받았을 때, 가장 배열에서 가장 큰 값을 pop해줘야 하는데 배열이 비어있는 경우 아무것도 나오지 않게 된다. 이를 방지하기 위해 for 루프를 돌때마다 우선순위가 입력값의 최댓값인 2^31을 갖는 0값을 put하였다. 또한, 절댓값이 같을 때는 음수를 우선적으로 출력해야 하므로, x가 음수일 경우 우선순위를 정할 때 단순히 절댓값을 넣는 것이 아니라 추가적으로 절댓값에 0.1을 빼주었다. 입력값은 정수이기 때문에 이렇게 하면 절댓값이 같을 경우에는 음수값이 먼저 pop되게 된다.