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

 

 

# 절댓값 힙. 처음의 값을 기억해야하지만 정렬은 절댓값으로 해야함.
from heapq import *
import sys
n = int(input()) # 입력 횟수
x_ls = [int(sys.stdin.readline()) for _ in range(n)] # 연산 리스트
heap = [] 
for x in x_ls: 
    if x == 0: # x가 0이면 = 출력해야함
        if len(heap) == 0: # 힙에 아무것도 없으면 0 출력
            print(0)
        else:# 힙의 길이가 1개 이상이면 절댓값이 가장 작은 값을 출력한다
            _, x = heappop(heap)
            print(x)
    else: # x가 0이 아닐때는 힙에 x의 절댓값과 x를 넣어줌
        heappush(heap, (abs(x), x))

 

생각보다 쉬웠던 문제! 실제 입력값과 절댓값을 모두 알아야 해서 튜플을 사용했다. 힙에서 튜플을 썼을때 어떻게 정렬되는지 궁금했는데 튜플의 첫번째 값을 기준으로 정렬이 된다고 한다. 그래서 절댓값을 앞에 넣어주고, 실제 입력값을 뒤에 넣어주는 형태로 튜플을 사용해 힙에 넣어주었다. 

 

 

 

 

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

11286번: 절댓값 힙