[programmers] 이중우선순위큐

Link

https://programmers.co.kr/learn/courses/30/lessons/42628

---

Code

import heapq

def solution(operations):
    minq = []
    maxq = []
    for oper in operations:
        op, num = oper.split(' ')
        if (op == 'I'):
            heapq.heappush(minq, int(num))
            heapq.heappush(maxq, -int(num))
        else:
            if (num == '1' and maxq):
                heapq.heappop(maxq)
                if (not maxq or -maxq[0] < minq[0]):
                    maxq = []
                    minq = []
            elif (num == '-1' and minq):
                heapq.heappop(minq)
                if (not minq or -maxq[0] < minq[0]):
                    maxq = []
                    minq = []
    if (minq and maxq):
        return [-maxq[0], minq[0]]
    else:
        return [0, 0]

---

Solution

minq와 maxq 두개를 통해 이중우선순위큐를 구현한다. 최대힙, 최소힙을 유지시키면서 최소값, 최대값을 관리, 만약 한쪽 힙이 비거나 최대힙의 값이 최소힙의 값보다 작으면 두 힙 모두 초기화를 시킨다. 그리고 두 힙이 모두 존재하면 최대값, 최소값을 리턴하고 아니면 [0, 0]을 리턴한다.