Koala - 7기/코딩테스트 준비 스터디

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

우롱티 2022. 8. 7. 23:31

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

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

문제분석

  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])을 통해 절댓값이 가장 작은 값을 출력한다.