[ PS / Python ] 42628. 이중우선순위큐

풀이.

이중 우선순위 큐는 최대값, 최소값을 삽입, 삭제할 수 있는 큐이다.
즉, 기준이 두개가 된다는 말이고.. 이 말은 그냥 두개의 힙을 사용해서 문제를 해결하면 된다.

max_heap, min_heap 으로 두 개의 힙을 사용하여, 최댓값을 삭제할 때는 max_heap 의 루트 노드가 타겟이 되고 최솟값을 삭제할 때는 min_heap 의 루트 노드가 타겟이 된다.

해당 타겟과 동일한 값을 각 힙에서 삭제하고, 다시 필요한 값은 집어넣는 방식으로 문제를 해결했다.

코드.

def solution(operations):

    import heapq

    max_heap = []
    min_heap = []

    while operations:
        operation = operations[0]

        cmd, num = operation.split()[0], int(operation.split()[1])

        if cmd == 'I':
            heapq.heappush(max_heap, -1 * num)
            heapq.heappush(min_heap, num)

        if cmd == 'D':
            if len(max_heap) == 0:
                operations = operations[1:]
                continue

            if num == -1:
                target = heapq.heappop(min_heap)
                temp = []
                while True:
                    t = heapq.heappop(max_heap)
                    if target != t*-1:
                        temp.append(t)
                    else:
                        break
                while temp:
                    heapq.heappush(max_heap, temp.pop())
            else:
                target = heapq.heappop(max_heap)
                temp = []
                while True:
                    t = heapq.heappop(min_heap)
                    if target != t*-1:
                        temp.append(t)
                    else:
                        break
                while temp:
                    heapq.heappush(min_heap, temp.pop())


        operations = operations[1:]

    if len(max_heap) == 0:
        return [0, 0]

    return [heapq.heappop(max_heap) * -1 , heapq.heappop(min_heap)]