백준-11286(파이썬)

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

11286번: 절댓값 힙

문제생각

 

문제에서 적어놓은 것처럼 힙 자료구조를 사용해야하는 문제였습니다.

그래서 저는 파이썬의 heapq 모듈을 사용하였습니다. 

하지만 이 문제는 단순히 heap 자료구조를 그대로 사용하면 안되는 것입니다.

 

문제에서 입력받는 수의 범위에는 음수도 포함되어있고 출력해야하는 값이 절댓값이 가장 작은 값을 출력해야되기 때문입니다. 또한 절댓값이 가장 작은 수가 여러개일 경우(-1, 1)에는 둘 중에 작은 값을 출력해야 합니다.

 

일단 파이썬의 heapq 모듈은 기본적으로 최소힙으로 동작합니다. 이 뜻은 heappop()을 할 때마다 최소값이 뽑힌다는 뜻입니다. 그래서 절댓값이 가장 작은 수가 여러개일 경우에 작은 값을 출력해야하는 경우는 해결되었습니다.

 

만약 입력으로 -2와 1이 입력되어있다고 가정하겠습니다. 이 때 기본적으로 heappop()을 한다면 당연히 -2가 뽑힐 것입니다. 하지만 문제에서는 절댓값이 가장 작은 값을 뽑으라고 했으니 1이 뽑혀야지 정상적으로 동작하는 것입니다.

 

따라서 이 문제에서는 입력과 동시에 우선순위를 줘야합니다.

 

그럼 우선순위를 어떻게 줘야할까요? 

 

저는 입력값의 절댓값을 우선순위로 주었습니다. 그럼 (2, -2), (1, 1) 이렇게 heap에 저장이 될 것이고 1의 우선순위가 더 높기에 1이 먼저 출력될 것입니다.

 

#heapq 모듈에서 우선순위 큐 만들기

  heappush(heap, (1, 입력값))

     => 입력을 튜플의 형태로하되 첫번째 인자를 우선순위로 사용할 수 있습니다.

 

문제코드

from heapq import heappush, heappop
import sys
import queue
input=sys.stdin.readline

n=int(input())
heap=[]
for i in range(n):
    x=int(input())
    if x!=0:
        #heap에 튜플에 형태로 push하면 튜플의 첫번째 원소가 우선순위의 기준이 된다.
        #그래서 입력의 절댓값을 넣어줌으로써 우선순위를 줬다.
        heappush(heap, (abs(x), x))
    else:
        if len(heap)==0:
            print(0)
        else:
            print(heappop(heap)[1])