[백준] 11286번 절댓값 힙 파이썬 정답 코드

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

11286번: 절댓값 힙

---

1. 접근 방식

• heapq의 heappush 시 튜플을 활용하자.

튜플을 사용하면 튜플의 원소별로 오름차순 정렬된다. 그리고 튜플의 원소 개수는 2개 이상도 가능하다.

아래는 heappush에서 튜플로 오름차순 정렬 기준을 설정한 예시 코드이다.

from heapq import heappush, heappop

heap = []

heappush(heap, (1, 2, "AA"))
heappush(heap, (1, 1, "A"))
heappush(heap, (2, 2, "BB"))
heappush(heap, (2, 1, "B"))
heappush(heap, (2, 3, "BBB"))

while heap:
    print(heappop(heap)[2])

코드를 실행하면 위와 같은 결과가 출력된다. 만약 인덱스 0을 기준으로 정렬할 때 똑같은 값이 존재한다면, 인덱스 1을 기준으로 그 값들을 오름차순 정렬한다. 이후 또 중복된다면 인덱스2를 기준으로 오름차순 정렬한다.

 

따라서 절대값 힙 문제에서는 가장 첫 번째 정렬 기준은 절대값이 작은 순이고, 두 번째 정렬 기준은 값이 작은 순이므로 튜플은 ( 값의 절대값, 값 )으로 구성하면 된다.

 

2. 정답 코드

from heapq import heappush, heappop
import sys

input = sys.stdin.readline

heap = []

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

    if not n :
        print(heappop(heap)[1] if heap else 0)
        continue

    heappush(heap, (abs(n), n))