이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 | 수신 탑(높이) |
---|---|
I 숫자 | 큐에 주어진 숫자를 삽입합니다. |
D 1 | 큐에서 최댓값을 삭제합니다. |
D -1 | 큐에서 최솟값을 삭제합니다. |
이중 우선순위 큐가 할 연산 operations
가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0]
비어있지 않으면 [최댓값, 최솟값]
을 return
하도록 solution
함수를 구현해주세요.
operations
는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.operations
의 원소는 큐가 수행할 연산을 나타냅니다.operations | return |
---|---|
["I 16","D 1"] | [0,0] |
["I 7","I 5","I -5","D -1"] | [7,5] |
Python의 라이브러리 heapq
를 사용하여 해결하였습니다.
heapq
는 기본적으로 최소힙이고, 최대힙으로 만들기 위해서는 (-num, num)
의 튜플 형태로 push
를 하여 우선순위를 역순으로 부여하면 됩니다.
처음에는 최소힙만을 사용하여 최대값을 제거해야하는 상황이면 list.pop()
을 통해 마지막 index를 제거하면 될 것이라 생각했습니다. 그래서 그렇게 구현을 하고 제출한 결과, 정답이 나왔습니다.
하지만 다시 생각해보니, 최소힙에서 마지막 index가 최대값이라는 보장이 없기 때문에 잘못된 구현 방식임을 인지하였습니다.
ex) ["I 10", "I 50", "I 20"] >> [10, 50, 20]
그리하여 최소힙, 최대힙 두 가지의 우선순위큐를 동시에 유지를 함으로써 최소값을 제거할 때는 최소힙에서 pop
을 한 값을 최대힙에서 remove
하고, 최대값을 제거할 때는 그 반대로 하면 됩니다. 최대힙에는 튜플 형태로 삽입이 되어있기 때문에 최소힙에서 remove
할 값 혹은 answer
에 넣기 위한 값은 index로 접근해야 합니다.
import heapq def solution(operations): min_hq = [] max_hq = [] for oper in operations: oper_split = oper.split(' ') direct = oper_split[0] num = oper_split[1] num = int(num) if direct == "I": heapq.heappush(min_hq, num) heapq.heappush(max_hq, (-num, num)) else: if len(min_hq) == 0: continue else: if num == -1: del_num = heapq.heappop(min_hq) max_hq.remove((-del_num, del_num)) else: del_num = heapq.heappop(max_hq) min_hq.remove(del_num[1]) answer = [] if len(min_hq) == 0: answer = [0, 0] else: answer = [max_hq[0][1], min_hq[0]] return answer