BOJ - 이중 우선순위 큐 [7662]

문제

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

핵심 로직

1. 최대힙, 최소힙 동시 사용

insert: 값을 넣을 때 최대힙, 최소힙에 해당값을 각각 넣어준다.

delete: 최대힙 혹은 최소힙에서 값을 제거할 때, 해당 값이 제거되었음을 기록해준다. → 다른 쪽 힙에서 값을 제거해줄 때 이미 제거된 값인지 확인하여, 이미 제거된 값인 경우 제거되지 않는 값이 나올 때까지 헤더 값을 계속해서 제거해 나간다.

Hint: 최대힙과 최소힙을 갖고 있는 "DoublePriorityQueue" 클래스와 힙에 넣을 값과 
해당 값의 제거 여부를 나타낼 수 있는 "Node" 클래스를 만들어 문제 해결 가능

아래 스켈레톤 코드 참고

import sys
import heapq

# __init__(), __lt__()를 제외한 private("__"로 시작하는) 메소드는 
# 코드 모듈화를 위해 만들었던 함수이므로, 구현 필수가 아님.
class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.is_deleted = False

    def delete(self):

    def __lt__(self, other):
        return self.value < other.value

class DoublePriorityQueue:
    def __init__(self) -> None:
        self.min_heap = []
        self.max_heap = []

    def insert(self, value):
        

    def pop_max(self):
        return 

    def pop_min(self):
        return 

    def __clear_deleted_head(self):
        

    def __is_empty(self, heap):
        return 

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    k = int(input())
    dpq = DoublePriorityQueue()
    for _ in range(k):
        command_line = input().rstrip().split()
        command = command_line[0]
        parameter = int(command_line[1]) if len(command_line) > 1 else 0

        if command == "I":
            dpq.insert(parameter)
        elif command == "D":
            if parameter == -1:
                dpq.pop_min()
            elif parameter == 1:
                dpq.pop_max()

    if len(dpq.max_heap) == 0:
        print("EMPTY")
    else:
        print(dpq.max_heap[0][1].value, dpq.min_heap[0][1].value)

 

정답 코드 - [시간복잡도: O(T * N^2*logN)]

import sys
import heapq


class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.is_deleted = False

    def delete(self):
        self.is_deleted = True

    def __lt__(self, other):
        return self.value < other.value


class DoublePriorityQueue:
    def __init__(self) -> None:
        self.min_heap = []
        self.max_heap = []

		# 시간복잡도: O(N*logN)
    def insert(self, value):
        self.__clear_deleted_head()
        node = Node(value)
        heapq.heappush(self.min_heap, (value, node))
        heapq.heappush(self.max_heap, (-value, node))
		
		# 시간복잡도: O(N*logN)
    def pop_max(self):
        if self.__is_empty(self.min_heap):
            return None

        node = heapq.heappop(self.max_heap)[1]
        node.delete()

        self.__clear_deleted_head()
        return node.value

		# 시간복잡도: O(N*logN)
    def pop_min(self):
        if self.__is_empty(self.min_heap):
            return None

        node = heapq.heappop(self.min_heap)[1]
        node.delete()

        self.__clear_deleted_head()
        return node.value

		# 시간복잡도: O(N)
    def __clear_deleted_head(self):
        while (True):
            if self.__is_empty(self.min_heap):
                break

            min_node = self.min_heap[0][1]
            if not min_node.is_deleted:
                break

            heapq.heappop(self.min_heap)

        while (True):
            if self.__is_empty(self.max_heap):
                break

            max_node = self.max_heap[0][1]
            if not max_node.is_deleted:
                break

            heapq.heappop(self.max_heap)

    def __is_empty(self, heap):
        return len(heap) == 0


input = sys.stdin.readline

T = int(input())
for _ in range(T):
    k = int(input())
    dpq = DoublePriorityQueue()
    for _ in range(k):
        command_line = input().rstrip().split()
        command = command_line[0]
        parameter = int(command_line[1]) if len(command_line) > 1 else 0

        if command == "I":
            dpq.insert(parameter)
        elif command == "D":
            if parameter == -1:
                dpq.pop_min()
            elif parameter == 1:
                dpq.pop_max()

    if len(dpq.max_heap) == 0:
        print("EMPTY")
    else:
        print(dpq.max_heap[0][1].value, dpq.min_heap[0][1].value)