백준 11286번 - 절댓값 힙

절댓값 힙 문제 바로 가기

풀이 날짜: 2026-01-20

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
import heapq

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

for _ in range(n):
    data = int(input())

    if data != 0:
        heapq.heappush(heap, (abs(data), data))
    else:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

문제 핵심 요약

이 문제는 숫자를 입력받아 저장하다가 0이 입력되면 특정 규칙에 따라 하나를 출력하는 문제다. 규칙은 절댓값이 가장 작은 수를 우선으로 하고, 절댓값이 같다면 실제 값이 더 작은 수를 우선으로 출력하는 것이다. 입력 크기가 크기 때문에 매번 정렬하는 방식은 비효율적이며, 우선순위 큐(힙)를 사용해야 한다.

“정렬”이 아니라 “우선순위 큐”

처음에는 리스트에 값을 모아 정렬하는 방식이 떠오를 수 있지만, 이 문제는 입력이 많고 0이 나올 때마다 즉시 결과를 출력해야 한다. 따라서 삽입과 삭제가 빠른 자료구조가 필요하다. 파이썬의 heapq는 최소 힙을 제공하며, 삽입/삭제가 O(log N)이므로 이 문제에 적합하다.

절댓값 힙의 핵심 아이디어

일반적인 힙은 “값이 작은 것”만 기준으로 정렬된다. 하지만 이 문제는 우선순위 기준이 두 개다.

1순위: 절댓값이 작은 수
2순위: 절댓값이 같다면 실제 값이 작은 수

이 두 기준을 동시에 만족시키기 위해, 힙에 숫자 하나를 그대로 넣지 않고 튜플 형태 (abs(x), x)로 포장해서 넣는다. 파이썬 힙은 튜플을 넣으면 앞 원소부터 순서대로 비교하므로, 문제의 조건이 자연스럽게 만족된다.

입력 처리와 힙에 값 넣기

입력된 값이 0이 아니라면, 이는 “저장” 명령이다. 이때 숫자를 (절댓값, 실제값) 형태로 힙에 넣는다. 이렇게 하면 힙 내부에서는 절댓값을 기준으로 정렬되고, 절댓값이 같을 경우 실제 값으로 자동 비교된다. 이 한 줄이 이 문제의 핵심 구현 포인트다.

heapq.heappush(heap, (abs(data), data))

헷갈렸던 점 정리

튜플에서 [1]을 출력하는 이유

힙에서 꺼낸 값은 예를 들어 (1, -1)과 같은 형태다. 여기서 1은 비교를 위한 절댓값이고, 실제 정답으로 출력해야 하는 값은 -1이다. 따라서 heappop(heap)[1]처럼 튜플의 두 번째 요소만 출력한다.

Vienna sausage