[백준-11286] 절댓값 힙

문제

링크

풀이

import heapq
import sys
input = sys.stdin.readline

n = int(input())
arr = []

for _ in range(n) :
    x = int(input())
    if x != 0 :
        heapq.heappush(arr, (abs(x), x))
        continue
    if len(arr) == 0 :
        print(0)
        continue
    min_value = heapq.heappop(arr)
    print(min_value[1])

힙을 이용한 우선순위 큐를 이용해 문제를 풀 수 있었다.

먼저 파이썬에서 힙은 값이 작은 수가 출력되는 최소 힙 구조를 가지고 있다.
그리고 문제에서 절댓값이 가장 작은 값을 출력하라고 했기 때문에 힙에 절댓값과 실제 값을 둘 다 넣으면 절댓값의 크기가 작은 노드가 먼저 출력되어 요구하는 조건을 만족할 수 있다.

입력받은 수가 0일 경우, heappush로 배열에 추가하고, 배열이 비어있을 경우 0을 출력했다.
그리고 입력받은 수가 0이 아니고, 배열의 길이가 0 이상일 경우, 현재 배열에서 절댓값이 작은 수를 찾고 heappop으로 출력한 후 배열에서 제거한다.

위 과정을 통해 코드를 작성할 수 있었다.