BOJ11286 절댓값 힙

문제

BOJ11286 절댓값 힙
실버I | 백준 11286 | Python3 파이썬 풀이

알고리즘

Heap은 Root 노드에 우선순위가 가장 높은 값이 온다. 기본적으로 Priority Queue나 Heap의 경우 작을 수록 우선순위가 높으므로, 가장 작은 값이 Root 노드에 온다.

하지만, 절댓값은 부호를 무시하므로, 값을 Heap에 넣어줄 때, 절댓값과 부호 정보를 함께 넣어준다.

즉, 2과 -3가 있을 때 힙에는 2와 3이 들어가며 절댓값은 2가 가장 작으므로 2가 나오게 되고, 이후에는 3이 나오고 원래 음수였으므로 -3이 나오게 되는 것이다.

시간 복잡도

• for loop : $O(N)$
• heap push or pop : $O(\log N)$

루프 내 한 스텝 당 push or pop이 한 번 발생하므로 시간복잡도는 $O(N\log N)$이다.

코드

import sys
import heapq

input = sys.stdin.readline

N = int(input())
# Heap
hq = []

for n in range(N):
    x = int(input())

    if x == 0:
        if hq:
            # 자동으로 절댓값이 가장 작은 값이 나온다
            x, i = heapq.heappop(hq)
            # 음수라면 -1이 곱해져 출력된다
            print(str(x * i))
        else:
            # 비어있다면 0 출력
            print('0')

    else:
        # 절댓값과 부호를 힙에 넣음
        if x < 0:
            # 음수
            heapq.heappush(hq, [-x, -1])
        else:
            # 양수
            heapq.heappush(hq, [x, 1])

결과