[BOJ] 11286 : 절댓값 힙 [우선순위 큐](Python)

문제 링크

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

11286번: 절댓값 힙

소스 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input().rstrip())

q = []
for i in range(n):
    num = int(input().rstrip())
    
    if num == 0:
        if q: print(heapq.heappop(q)[1])
        else: print(0)
    else: # 절댓값과 실제값을 튜플로 추가
        heapq.heappush(q,(abs(num),num))

 

해설

• 절댓값 힙, 우선순위 큐

리스트의 첫 번째 원소가 최소가 되는 것을 보장하는 파이썬의 최소힙 알고리즘이다.

다만 절댓값을 기준으로 작은 값을 반환할 수 있도록 튜플 형태로 리스트에 추가했다.

힙추가를 할 때 튜플로 추가를 하게 되면, 튜플의 첫 번째 원소를 기준으로 정렬을 수행한다.

 

예시

예를 들어 -1 과 1 을 둘 다 q에 넣는다면, [(1,-1), (1,1)] 형태로 리스트가 구성될 것이다.

여기에서 heappop을 하게 되면 가장 왼쪽의 원소가 반환되는데(절댓값을 기준으로 가장 작은 값이 반환) 우리가 출력할 것은 절댓값이 아니므로 뽑아낸 튜플의 [1] 번 인덱스를 출력해야 한다.

 

 

그 이외의 과정은 최소힙을 구현하는 것과 다를 것이 없다.

 

#BOJ #백준 #알고리즘 #Python #파이썬