[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/42628
📌문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때,
모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면
[최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
입출력 예 설명
16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.
💡 문제 풀이
문제에서 우선순위 큐를 언급하였지만 최소항목을 빼내는 자료구조이다보니 최대값 처리에 대한 이슈가 생겨서, 자주 사용하는 deque 자료구조를 사용하여 풀어보았다.
- numbers : 숫자를 담거나 빼는 deque
간단하게 명령어에 맞게 deque에 숫자를 추가하거나 삭제(최대값, 최소값)하면 된다.
- "I"의 경우 숫자를 append
- "D"의 경우 최대값(max), 최소값(min) remove
코드는 아래와 같다.
deque 이용
from collections import deque
def solution(operations):
numbers = deque([])
for oper in operations:
order, num = oper.split(' ')
if order == "I":
numbers.append(int(num))
else:
if not len(numbers): continue
if num == '1':
numbers.remove(max(numbers))
else:
numbers.remove(min(numbers))
return [max(numbers), min(numbers)] if len(numbers) else [0, 0]다음으로 문제에서 언급한 **우선순위 큐** 자료 구조를 이용하여 해결하였다.
우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조다.
파이썬에서는 heapq 모듈을 통해 우선순위 큐 자료구조를 구현하였다.
※여기서 heap이란 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리를 말한다.
heapq 모듈에는 heappush, heappop, heapify 등의 함수를 제공한다.
함수에 대한 자세한 설명과 활용예시는 공식 사이트에서 확인할 수 있다.
우선순위 큐를 사용한 문제풀이는 다음과 같다.
step 1)
우선순위 큐는 가장작은 항목(최소값)을 빼내기 때문에 최대값을 빼내기 위한 작업이 필요하다.
이를 위해서 최소, 최대값을 다루는 두 개의 heap을 생성한다.
- max_heap : 최대값을 다루는 heap
- min_heap : 최소값을 다루는 heap
step 2)
"I"의 명령어는 단순 삽입이기 때문에 숫자를 max_heap, min_heap에 모두 추가해준다.
이 때 max_heap에는 최대값이 먼저 나올 수 있도록 숫자에 마이너스(-)를 붙여 heappush 해준다.
step 3)
"D"의 경우 1은 최대값이므로 max_heap을 -1은 최소값이므로 min_heap으로 나누어 진행한다.
이 때 최대값과 최소값을 서로 다른 heap에 빼내고 있기 때문에 각 heap을 최신화로 유지시켜 비교할 필요가 있다.
ex)
min_heap : [10, 20, 30, 40]
max_heap : [10, 20, 30, 40]
으로 똑같이 삽입한 상태에서 "D 1" 명령어를 4번 실행하면
min_heap : [10, 20, 30, 40]
max_heap : []
이 되므로 문제가 발생한다.
따라서 heappop을 진행할 때는 아래의 두 가지 경우에 대해 주의한다.
1. ex) 예시처럼 heap이 비워진 상태일 때
2. -max_heap[0] < min_heap[0] → max_heap에서의 첫 번째 값(최대값)이 min_heap에서의 첫 번째 값(최소값)보다 작을 때
위 두 가지 경우에 대해서는 max_heap, min_heap을 빈 리스트로 초기화해준다.
코드는 아래와 같다.
우선순위 큐(heapq) 이용
from heapq import heappush, heappop
def solution(operations):
max_heap = []
min_heap = []
for oper in operations:
if oper == "D 1":
if max_heap != []:
heappop(max_heap)
if max_heap == [] or -max_heap[0] < min_heap[0]:
min_heap = []
max_heap = []
elif oper == "D -1":
if min_heap != []:
heappop(min_heap)
if min_heap == [] or -max_heap[0] < min_heap[0]:
max_heap = []
min_heap = []
else:
num = int(oper[2:])
heappush(max_heap, -num)
heappush(min_heap, num)
if min_heap == []:
return [0, 0]
return [-heappop(max_heap), heappop(min_heap)]