[Programmers/ level3] 이중우선순위큐
👩문제
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
| 명령어 | 수신 탑(높이) |
|---|---|
| I 숫자 | 큐에 주어진 숫자를 삽입합니다. |
| D 1 | 큐에서 최댓값을 삭제합니다. |
| D -1 | 큐에서 최솟값을 삭제합니다. |
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
👩제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
👩입출력 예
| operation | return |
|---|---|
| [“I 16”,”D 1”] | [0,0] |
| [“I 7”,”I 5”,”I -5”,”D -1”] | [7,5] |
🙋♀️내 풀이: heap 사용
우선 명령어에 따라서 최대값/최소값 삭제가 이루어지므로 해당 연산이 빠르게 이루어질 수 있는 heap을 사용해야 한다 생각했다.
heap을 구현하기 위해서 heapq를 사용하였다. heapq에 대해서는 다음 게시글에서 자세히 다루었으니 참고하길 바란다!!
여기서 고려해야 할 점은 어떻게 최댓값을 제거할 것인가이다. 단순히 힙의 가장 마지막 원소가 최대값이 아니라는 점을 주목해야 한다.
처음 나는 다음과 같이 알고리즘을 작성하였다.
import heapq
def solution(operations):
heap = []
for i in operations:
op, val = i.split(" ")
if op == "I":
heapq.heappush(heap, int(val))
elif len(heap) > 0 and val == "-1":
heapq.heappop(heap)
elif len(heap)> 0 and val == "1":
if len(heap) == 1:
heap.pop()
else:
a = heap[-1]
b = heap[-2]
if a>b: heap.pop(-1)
else: heap.pop(-2)
heapq.heapify(heap)
return [0,0] if len(heap) == 0 else [max(heap[-1], heap[-2]), heap[0]]
🙄 처음 위와 같이 최대값을 삭제할 때 마지막 두 원소만을 비교해 큰 값을 최대값으로 판단하였고, 해당 풀이가 정답처리가 되었다…!!
하지만 다음과 같은 경우, 이 풀이는 옳지 않다는 것을 깨닫게 되었다.
다른 사람들의 풀이를 확인하면서 두 힙을 두는 풀이가 효율적이라는 것을 알 수 있었다. 그렇다면 다음 알고리즘도 확인해보자!
🙋♀️다른 풀이1: 최대힙, 최소힙
우선 최대값을 삭제하기 편한 최대힙 하나, 최소값을 삭제하기 편한 최소힙 하나를 둔다.
☝️ 값을 넣을 때는 최대힙, 최소힙 모두에 넣는다. 단, 최대힙에는 -값을 넣음으로써 최대값이 가장 앞에 존재하도록 한다.
✌️ 최소값을 삭제할 때는 최소힙에서 heappop을, 최대값을 삭제할 때는 최대힙에서 heappop을 진행한다.
- 단! 🌟힙의 동기화🌟를 해주어야 한다!!
- 삭제하는 값이 다른 힙에서도 삭제되도록 remove를 사용한다.
- remove를 사용할 경우, 힙 구조가 깨질 수 있으므로 🌟heapify🌟를 적용한다.
from heapq import heappush, heappop, heapify
def solution(arguments):
max_heap = []
min_heap = []
for i in arguments:
op, val = i.split(" ")
if op == "I":
heappush(max_heap, -int(val))
heappush(min_heap, int(val))
elif op == "D":
try:
if val == "1":
min_heap.remove(-max_heap[0])
heapify(min_heap)
heappop(max_heap)
else:
max_heap.remove(-min_heap[0])
heapify(max_heap)
heappop(min_heap)
except:
continue
if len(max_heap) == 0:
return [0, 0]
else:
return [-heappop(max_heap), heappop(min_heap)]
🙋♀️다른 풀이2: heaq.nlargest 함수 사용
heaq에서는 n개의 가장 큰 요소/ 가장 작은 요소들로 구성된 리스트를 반환하는 함수가 존재한다.
👩 heapq.nlargest(n, iteralbe, key= None)
- 데이터 내 n개의 가장 큰 요소로 구성된 리스트를 반환한다.
- key: 각 요소 비교 key를 설정할 수 있다.
- key = str.lower일 경우, sorted(iterable, key= key, reverse = True)[:n]과 동일하다.
👩 heapq.nsmallest(n, iterable, key= None)
- 데이터 내 n개의 가장 작은 요소로 구성된 리스트를 반환한다.
- key: 각 요소 비교 key를 설정할 수 있다.
- key = str.lower일 경우, sorted(iterable, key= key, reverse = True)[:n]과 동일하다.
import heapq
def solution(m, n, puddles):
lst = [1, 5, 6, 8, 9]
print(heapq.nlargest(2, lst, key = lambda x: -x)) # [1, 5]
print(heapq.nlargest(1, lst)) # [9]
print(heapq.nsmallest(3, lst)) # [1, 5, 6]
👩 heapq.nlargest를 사용한 풀이
import heapq
def solution(operations):
heap = []
for i in operations:
op, val = i.split(" ")
if op == "I":
heapq.heappush(heap, int(val))
elif len(heap) > 0:
if val == "1":
heap.pop(heap.index(heapq.nlargest(1, heap)[0])) #가장 큰 값의 인덱스를 사용해서 값 삭제
heapq.heapify(heap) #삭제 후 힙 재정렬
else:
heapq.heappop(heap)
if len(heap) == 0:
return [0, 0]
else:
return [max(heap), heap[0]]
🙇♀️풀이에 부족한 부분이 있다면 말씀해주세요! 감사합니다!
댓글남기기