[백준 파이썬] 11286 절댓값 힙

📌문제 출처

백준 단계별 문제풀이 - 우선순위 큐
https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

❓ 문제

❗ 풀이

• heap 자료구조 활용

📗 풀이 코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

nums = []
for _ in range(int(input())):
    i = int(input())
    if i :
        p_m = -1 if i <0 else 1
        heappush(nums,[i*p_m,p_m])
    else :
        if not nums:
            print(0)
        else :
            out = heappop(nums)
            print(out[0]*out[1])

📗 코드 해설

• heappush로 nums라는 list에 list를 원소로 추가하며 heap 구조로 변경한다.
• heappop 시 list의 크기는 첫번째 원소를 기준으로 우선 정렬된다.
• 따라서 heappush를 해줄 때 [입력값의 절댓값, 원래 입력값의 부호] 형태로 추가한다.
• 이후 heappop 진행 시 절댓값이 낮은 순서로 출력이 되며, 출력 시에 원래 부호를 곱해준다.