❓ 프로그래머스 : 이중우선순위큐
〽️ 문제 요약
주어진 숫자를 삽입하는 연산, 큐에서 최댓값을 삭제하는 연산, 큐에서 최솟값을 삭제하는 연산을 할 수 있는 이중 우선순위 큐를 구현하면 되는 문제
🤨 접근법
테스트 케이스들이 효율성을 적당히 고려 안해도 통과할 수 있게 구성되어 있어서 리스트나 덱을 활용한 큐로 삽입 / 인덱스 삭제 연산을 구현하여도 통과하는 문제다.
하지만 문제 취지에 맞게 힙을 활용해서 이중 우선순위 큐를 구현해보고자 하였지만 실패해서 여러 레퍼런스를 참고했다.
효율성 측면에서 제한이 널널하기 때문에 매번 힙을 초기화 해주는 등의 여러 방법이 있었지만 가장 간단하고 효율적으로 이중 우선순위 큐를 구현한 레퍼런스의 풀이를 정리하였다.
if min_heap:
if value == '1':
min_heap.pop(min_heap.index(nlargest(1, min_heap)[0]))
else:
heappop(min_heap)파이썬의 heapq 모듈에는 nlargest라는 메소드가 존재한다. 힙에서 1~n번째로 큰 원소까지 나열한 리스트를 반환해준다. 따라서 기본적으로 우선순위 큐를 최소 힙으로 구현하되, 최대값을 삭제하는 연산에서는 힙에서 nlargest(1, min_heap)의 첫 번째 값에 해당하는 인덱스를 삭제하는 방법으로 효율적인 연산을 수행할 수 있다. 여기에 따르면 nlargest 메소드의 시간 복잡도는 n = t일 때 O(t*logn)의 시간복잡도를 갖는다.
🔡 코드
from heapq import heappush, heappop, nlargest
def solution(operations):
min_heap = []
for operation in operations:
op, value = operation.split()
if op == 'I':
heappush(min_heap, int(value))
else:
if min_heap:
if value == '1':
min_heap.pop(min_heap.index(nlargest(1, min_heap)[0]))
else:
heappop(min_heap)
return [nlargest(1, min_heap)[0], min_heap[0]] if min_heap else [0, 0]📚 고찰
문제를 봤을 때 쉽고 비효율적으로 풀이할 수 있는 방법과 어렵고 효율적으로 풀이할 수 있는 방법 두 가지가 모두 떠올랐을 때 먼저 쉬운 풀이부터 구현해놓은 뒤 어려운 풀이를 해보는 게 시간적인 측면에서 나을 것 같다는 생각이 들었다. 시험에서는 일단 제출은 해야되니까??
최소 힙으로 우선순위 큐를 구현했을 때 최댓값을 삭제하는 연산은 꽤 유용하게 쓰일 수 있을 듯 하다.
