백준 11286번: 절댓값 힙 [python]

난이도 : 실버 1
유형: 우선순위 큐
https://www.acmicpc.net/problem/11286

문제 접근

n번 x를 입력받을건데
x가 0이 아니라면 배열에 x를 추가할것이고
x가 0 이라면 배열에서 절댓값이 가장 작은 요소를 출력및 제거한다.
(단 절댓값이 가장 작은 요소가 여러개라면, 그중 가장 작은 수를 출력 및 제거 해준다.그리고 배열이 비었는데 0을 받으면 0 출력해준다.)

파이썬에서 절댓값은 abs() 함수안에 수를 넣으면 된다.

처음엔 heapq 리스트 전체를 abs() 안에 넣으려고 했다가 오류가 났다.
abs() 안에는 리스트가 들어갈 수 없다.

포인트는 heap 안에 요소를 push할때 튜플 형태로 푸시하는 것이다.
heapq.heappush(heap, (abs[x], x))
이러면 힙에 (x의 절댓값, x) 형식으로 들어간다.

heapq에 튜플을 넣고 pop을 하면?
튜플에 인덱스 0 번째를 기준으로 작은걸 꺼내준다.
만약 인덱스 0이 같다면 그다음 인덱스 1을 비교하여 더 작은걸 꺼내준다.

고로 print 할때만 두번쨰 요소(실제값) 을 해주면 된다.

해답 및 풀이

import heapq
import sys
input = sys.stdin.readline

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

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

    if x != 0:
        heapq.heappush(heap, (abs(x), x))
    elif x == 0:
        if heap:
            print(heapq.heappop(heap)[1])  #두번 쨰 요소를 출력, 그러나 내부적으로 0번쨰 인덱스(절댓값)도 비교하긴 한다.    
        
        else:
            print(0)