[백준/파이썬] 11286번 절댓값

※ 문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

※ 입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

※ 출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

※ 해결방법

이 문제를 해결하기 위해서는 우선순위 큐(priority queue)를 구현해야한다. 우선순위 큐는 일반적인 큐와는 달리, 요소들이 특정 우선순위에 따라 정령되어 처리되는 자료구조이다.

 

파이썬에서 우선순위 큐를 나타내는 방법은 'PriorityQueue'가 있다.

• put(item) : 요소를 큐에 추가한다. 'item'은 큐에 추가될 데이터이며, 일반적으로 튜플형식으로 우선순위와 데이터를 함께 넣는다.
• get() : 큐에서 우선순위가 가장 높은 요소를 제거하고 반환한다. 큐가 비어 있으면 큐에 요소가 추가될 때 까지 기다린다.
• empty() : 큐가 비어 있는지 확인한다. 비어 있으면 'True', 그렇지 않으면 'False'를 반환한다.
• qsize() : 현재 큐에 들어 있는 요소의 개수를 반환한다.

queue = priorityqueue()

queue.put(abs(request),request)에서 request값이 1과 -1이면 오름차순으로 순서가 지정이 되어 원하는 대로 작동시킬 수 있으며, abs()를 사용하여 절댓값을 나타낼 수 있도록 하였다.

 

처음에 PriorityQueue를 사용하여 코딩을 진행하였다.

import sys
from queue import PriorityQueue
input = sys.stdin.readline

n = int(input())
queue = PriorityQueue()
for i in range(n):
    m = int(input())
    if m != 0:
        queue.put((abs(m), m)) 
    else:
        if queue.empty(): 
            print(0)
        else:
            temp = queue.get()
            print(temp[1])

 

하지만 보통 사람들은 'PriorityQueue' 보다 'heapq'를 사용하고 있었다.

 

PriorityQueue와 headq의 차이

'PriorityQueue'는 'heapq'보다 더 많은 기능을 제공한다. 특히 멀티스레드 환경에서 안전하게 사용될 수 있도록 설계가 되어있다. 하지만 'heapq'는 멀티스레드 안전성을 제공하지 않으며, 직접 리스트를 힙처럼 사용해야한다는 단점이 있지만 가볍고 단순해서 멀티스레드 환경이 아닐 때는 'heapq'를 사용하는 것이 효율적이라고 한다.

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

n = int(input())
heap = []
for i in range(n):
    m = int(input())
    if m != 0:
        heappush(heap,(abs(m),m))
    else:
        if not heap: 
            print(0)
        else:
            print(heappop(heap)[1])