개발/algorithm

[백준 11286] 절댓값 힙 - python

zzi_on2 2022. 2. 16. 15:43

문제 링크

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

 

11286번: 절댓값 힙

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

www.acmicpc.net

풀이 

- heapq 사용해서 우선순위 큐를 구현하였다. 

- 입력된 숫자의 절댓값이 우선순위가 되므로 heap에 (절댓값, 원소)를 넣어준다. 

- 0이 입력되면 heap에서 우선 순위가 가장 높은 것을 빼준다. 

import heapq 
import sys 
input = sys.stdin.readline 

n = int(input())

heap = []

for _ in range(n):
  num = int(input())

  if num != 0:
    heapq.heappush(heap, (abs(num), num))
  else:
    if heap:
      print(heapq.heappop(heap)[1])
    else:
      print(0)