문제 출처 : https://www.acmicpc.net/problem/11286

---

문제 파악

이전 글(11279 최대 힙)에서 최소 힙/최대 힙 개념과 heapq 사용법을 학습했다.

이번 문제는 형태가 조금 다르다.

절댓값이 가장 작은 값을 꺼내야 하고,
절댓값이 같다면 실제 값이 더 작은 숫자(즉, 음수)를 우선으로 해야 한다.

즉, 아래 두 가지 규칙을 만족해야 한다.

1. 비교 기준 1순위 → abs(x)
2. 비교 기준 2순위 → x (절댓값이 같을 때는 더 작은 실제값 우선)

그리고 꺼낸 값은 출력 + 배열에서 제거해야 한다.
배열이 비어 있다면 0 출력.

처음에는 최소힙/최대힙 두 개를 활용할까 고민했지만,
결국 이 문제는 힙 하나로 해결할 수 있다.

해답 아이디어

heapq에는 중요한 특징이 있는데

튜플을 push하면, 튜플의 첫 번째 요소로 비교하고, 동일하면 두 번째 요소로 비교한다.

그래서 간단하게 튜플에 절댓값과 실제값 두개를 묶어서 push 해주면 된다.

heapq.heappush(arr,(abs(x),x))
(abs[x],x) 이렇게 튜플로 묶어서 저장해주면
딱 우리가 원하는 정렬 규칙과 맞아떨어진다.

1. 절댓값이 더 작은 값
2. 절댓값이 같다면 실제 값이 더 작은 값

비교는 abs[x]로, 출력은 x로 해줄 수 있다.

해답 및 풀이

import heapq
import sys
input = sys.stdin.readline

N = int(input())

arr = []

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

    # 배열에서 절댓값이 가장 작은 값 출력(절댓값이 같다면 실제값이 더 작은 수 출력) 
    # and 그 값 배열 제거 (만약 배열이 비어있다면 0출력)
    if x == 0:
        # 비어있다면 0 출력
        if not arr:
            print(0)

        # 배열에서 절댓값이 가장 작은 값 출력(같다면 실제값 더 작은 수 출력)
        else:
            min_value = heapq.heappop(arr)
            print(min_value[1])
    # 배열에 x 값 추가    
    else:
    	# 절댓값과 실제값을 동시에 저장
        heapq.heappush(arr,(abs(x),x))

---

정리

• 문제의 정렬 기준은
  1순위: abs(x)
  2순위: x (실제값)

• 파이썬 heapq는 튜플 비교를 지원 → (abs(x), x)로 한 번에 해결 가능

• pop 시 출력해야 하는 값은 tuple[1](실제값)