[Python] 11286 - 절댓값 힙

[Silver I] 절댓값 힙 - 11286 

[문제 링크](https://www.acmicpc.net/problem/11286) 

🗝️알고리즘 분류

• 자료구조
• 우선순위 큐

---

💻문제 정의

0이 아닌 정수를 입력받으면 배열에 저장하고, 0을 입력 받으면 배열 내 절댓값이 가장 작은 값을 출력하고 배열에서 제거한다. 절댓값이 같은 값이 여러 개 일 경우, 가장 작은 값을 출력하는 프로그램을 작성하는 문제이다.

 

💡접근 및 설계

해당 배열은 우선순위 큐를 구현함으로써 다음의 연산을 수행할 수 있다. 파이썬에서 우선순위 큐를 구현하는 방법은 두 가지이다. 

 

1. PriorityQueue

파이썬의 PriorityQueue 라이브러리를 활용하여 우선순위 큐를 구현할 수 있다. 

from queue import PriorityQueue

T = int(input())

Q = PriorityQueue()

def priority_queue(num):
    if (num != 0):
        Q.put([abs(num), num])
        
    else:
        if Q.empty():
            print(0)
        else:
            print(Q.get()[1])

for _ in range(T):
    priority_queue(int(input()))

PriorityQueue는 기본적으로 작은 숫자에 대해 우선순위가 높다고 인지한다.

 

문제의 예제 입력을 예시로 들었을 때 -1과 1중 우선순위는 -1이 높을 것이다. 하지만 -2와 1중에선 -2가 우선순위가 높지만, 우리가 원하는 결과는 1이 우선순위가 더 높아야 한다. 즉, 입력 숫자와 절댓값을 함께 큐에 저장한다.

 

-1와 1에 대해서 [1, -1] 과 [1, 1] 의 우선순위를 비교하면 [1, -1]의 우선순위가 더 높을 것이다.

 

1와 -2에 대해서 [1, 1] 과 [2, -2] 의 우선순위를 비교하면 [1, 1]의 우선순위가 더 높을 것이다.

 

2. heapq

일반적으로 우선순위 큐는 heap을 이용하여 구현할 수 있다. 파이썬에선 heapq 라이브러리를 이용하여 우선순위 큐를 구현할 수 있다.

 

import heapq

T = int(input())

heap = []

def abs_heap(num):
    if (num != 0):
        heapq.heappush(heap, [abs(num), num])

    else:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

for _ in range(T):
    abs_heap(int(input()))

 

기본적인 동작은 PriorityQueue에서와 동일하다. 절댓값과 입력값을 함께 저장하여 우선순위를 메기도록 하여 출력한다.

 

🗒️제출 코드

# 11286 절댓값 힙 (힙)

import heapq

T = int(input())

heap = []

def abs_heap(num):
    if (num != 0):
        heapq.heappush(heap, [abs(num), num])

    else:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

for _ in range(T):
    abs_heap(int(input()))

# 11286 절댓값 힙 (우선순위 큐, 시간 초과)

from queue import PriorityQueue

T = int(input())

Q = PriorityQueue()

def priority_queue(num):
    if (num != 0):
        Q.put([abs(num), num])
        
    else:
        if Q.empty():
            print(0)
        else:
            print(Q.get()[1])

for _ in range(T):
    priority_queue(int(input()))

---