[백준/Python] 11286번 절댓값 힙

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

11286번: 절댓값 힙

 

문제분석

1. 분류
   • 자료구조, 우선순위 큐
2. 문제설명
   • 배열에 정수 x(x ≠ 0)를 넣는다.
   • 입력에서 0이 주어지는 횟수만큼 답을 출력한다.
   • 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
   • 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

코드

1	import heapq
2	from sys import stdin
3
4	N=int(input())
5	heap=[]
6	for _ in range(N):
7	x=int(stdin.readline())
8	if x==0:
9	if heap:
10	print(heapq.heappop(heap)[1])
11	else:    #배열이 비어있는 경우
12	print(0)
13	else:
14	heapq.heappush(heap, (abs(x), x))

 

문제풀이

• 절댓값을 기준으로 힙을 정렬하여 구성한다. → heapq.heappush(heap, (abs(x), x))
• 힙에 원소를 추가할 때 (-i, i)의 튜플형태로 넣어주면 튜플의 첫 번째 원소를 기준으로 힙을 구성하게 된다.
• 출력해야 하는 값은 1번째 자리에 저장되어 있으므로 print(heapq.heappop(heap)[1])을 통해 절댓값이 가장 작은 값을 출력한다.