[백준/Python] 11286 : 절댓값 힙

 

 

이번 문제는 앞서 풀었던 최대힙, 최소힙과 유사한 문제이지만 추가로 절댓값이 조건으로 추가된 문제이다.

 

import sys
import heapq
N = int(input())
heap = [] # 비어있는 배열에서 시작

for _ in range(N):
    calc = list(map(int, sys.stdin.readline().split()))
    for num in calc:
        if num == 0:
            if heap: print(heapq.heappop(heap)[1])
            else: print(0)
        else: heapq.heappush(heap, (abs(num), num))

 

heappush로 숫자를 삽입할 때 튜플을 이용하는 것이 포인트였다.

 

파이썬의 절댓값 내장함수 abs()를 사용해서 절댓값인 값과 원본 값을 tuple 쌍으로 묶어주면, 이후 heappop 시 맨 앞 숫자를 기준으로 정렬해주기 때문에 이와 같이 구현할 수 있다. 

 

heap의 중간 단계를 출력해본 예시인데, 숫자 num이 들어올때 (num의 절댓값, num) 이런 튜플 쌍으로 들어온다는 말이다.

즉 처음에 1이 들어오면 (1,1)이 들어갔고, 두 번째로 -1이 들어왔을 때는 (1, -1)이 들어온 것을 확인할 수 있다.

 

튜플들이 들어온 heap에 대해서 heappop(heap)[1]을 작성해주면 튜플 쌍의 0 번째 원소로 먼저 정렬을 한 뒤, 튜플 쌍의 두 번째 값 (1번째 원소) 이 원본 num이기 때문에 이를 출력해주게 되는 것이다!