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

위 문제의 핵심을 절대값을 인덱스로 가지며 기존의 값을 가지고 있어야 한다는 점입니다.

 

문제

 

 

코드

import sys, heapq as hq

input = sys.stdin.readline

n = int(input())
ls = []
for _ in range(n):
    num = int(input())
    if num == 0:
        print(hq.heappop(ls)[1] if ls else 0)
    else:
        hq.heappush(ls, (abs(num), num))

 

 

설명

heapq 모듈을 import 합니다

절대값을 구해야 하기 때문에 튜플의 형태로 넣습니다

그렇게 되면 기존의 값 (절댓값, 실제값)의 형태로 힙에 저장되게 됩니다

 

그 뒤 절대 값을 기준으로 정렬된 힙에 실제 값을 print 합니다

 

 

예시

 

10 1 -1 0 0 0 1 1 -1 -1 2

 

이 입력을 처리하면서 힙의 상태 변화를 살펴보겠습니다.

1. 입력 1:
   • 절대값: 1, 원래 값: 1
   • 힙 상태: [(1, 1)]
2. 입력 -1:
   • 절대값: 1, 원래 값: -1
   • 힙 상태: [(1, -1), (1, 1)] (원래 값 -1이 1보다 작기 때문에 앞에 옴)
3. 입력 0 (첫 번째 0):
   • 힙에서 최솟값 (1, -1) 제거
   • 출력: -1
   • 힙 상태: [(1, 1)]
4. 입력 0 (두 번째 0):
   • 힙에서 최솟값 (1, 1) 제거
   • 출력: 1
   • 힙 상태: []
5. 입력 0 (세 번째 0):
   • 힙이 비어있으므로 출력: 0
6. 입력 1:
   • 절대값: 1, 원래 값: 1
   • 힙 상태: [(1, 1)]
7. 입력 1:
   • 절대값: 1, 원래 값: 1
   • 힙 상태: [(1, 1), (1, 1)]
8. 입력 -1:
   • 절대값: 1, 원래 값: -1
   • 힙 상태: [(1, -1), (1, 1), (1, 1)]
9. 입력 -1:
   • 절대값: 1, 원래 값: -1
   • 힙 상태: [(1, -1), (1, -1), (1, 1), (1, 1)]
10. 입력 2:
    • 절대값: 2, 원래 값: 2
    • 힙 상태: [(1, -1), (1, -1), (1, 1), (1, 1), (2, 2)]