[7662] 이중 우선순위 큐

[알고리즘 개요] 이중 우선순위 큐 (Double Priority Queue)

일반적인 우선순위 큐는 최소값이나 최대값 중 하나만 빠르게 추출할 수 있음. 하지만 이 문제처럼 양방향에서 데이터를 삭제해야 할 때는 두 개의 힙(Min-Heap, Max-Heap)을 동시에 운용하는 전략이 필요함.

1. 핵심 아이디어: 동기화(Synchronization)

최소 힙에서 삭제된 데이터가 최대 힙에는 여전히 남아있는 현상이 발생함. 이를 해결하기 위해 checked (또는 visited) 배열을 도입하여 각 데이터의 유효성을 관리함.

• 데이터 삽입: 삽입되는 각 데이터에 고유한 ID(인덱스)를 부여하여 두 힙에 모두 넣고, checked[ID]를 True로 설정함.
• 데이터 삭제: 최대값 삭제 시 Max-Heap에서 꺼낸 뒤, 해당 ID의 checked가 True인지 확인.
  • 이미 다른 힙(Min-Heap)에서 삭제된 데이터(False)라면 무시하고 다음 데이터를 꺼냄(유령 값 제거).
  • 유효한 데이터를 찾으면 checked[ID]를 False로 바꿔 양쪽 모두에서 삭제되었음을 표시함.

---

2. 단계별 접근 방식

① 자료구조 준비

• minq: 최소값을 찾기 위한 최소 힙.
• maxq: 최대값을 찾기 위한 최대 힙 (Python의 heapq는 최소 힙만 지원하므로 값을 음수로 변환하여 저장).
• checked: 데이터의 삭제 여부를 기록하는 불리언 리스트.

② 명령 처리

• I (Insert): (값, ID) 형태의 튜플로 두 힙에 각각 푸시. ID는 0부터 순차적으로 증가함.
• D 1 (Delete Max): maxq의 루트가 이미 삭제된 값인지 확인하며 pop. 유효한 값을 찾으면 checked[ID]를 False로 변경.
• D -1 (Delete Min): minq의 루트가 이미 삭제된 값인지 확인하며 pop. 유효한 값을 찾으면 checked[ID]를 False로 변경.

③ 최종 정리 (Cleaning)

• 모든 연산이 끝난 후에도 각 힙의 TOP에 이미 삭제된 '유령 데이터'가 남아있을 수 있음.
• 출력 전 마지막으로 checked를 확인하며 양쪽 힙의 루트가 유효하도록 정리해줌.

---

3. 복잡도 분석

• 삽입: O(log N)
• 삭제: 유령 값을 건너뛰는 과정이 포함되지만, 각 원소는 각 힙에서 최대 한 번씩만 삭제되므로 평균적으로 O(log N)임.

---

4. 주의사항 및 팁

• Python의 sys.stdin.readline 사용은 필수 (입력 데이터가 많아 속도 차이가 큼).
• maxq에서 값을 꺼낼 때는 다시 부호를 반전시켜 원래의 값을 복원해야 함.
• 빈 큐일 경우 "EMPTY" 출력을 잊지 말 것.

 

 

import sys

import heapq

# help(dir(heapq))

input = sys.stdin.readline

T = int(input())

while T:

    # n 입력 받음

    N = int(input())

    minq = []

    maxq = []

    checked = [False] * N

    for i in range(N):

        # I 면 삽입, D면 삭제 1이면 최대 -1이면 최소

        cmd, num = input().strip().split()

        num = int(num)

        if cmd == "I":

            # 삽입 시 (값, 인덱스) 형태로 삽입

            heapq.heappush(minq, (num, i))

            heapq.heappush(maxq, (-num, i))

            # 방문 처리

            checked[i] = True

        elif cmd == "D":

            if num == 1:

                # 유령 값 제거(실존X)

                while maxq and not checked[maxq[0][1]]:

                    heapq.heappop(maxq)

                # 방문처리 및 값 제거

                if maxq:

                    checked[maxq[0][1]] = False

                    heapq.heappop(maxq)

            else:

                while minq and not checked[minq[0][1]]:

                    heapq.heappop(minq)

                if minq:

                    checked[minq[0][1]] = False

                    heapq.heappop(minq)

    # 유령 처리

    while minq and not checked[minq[0][1]]:

        heapq.heappop(minq)

    while maxq and not checked[maxq[0][1]]:

        heapq.heappop(maxq)

    # 출력

    if maxq and minq:

        print(f"{-maxq[0][0]} {minq[0][0]}")

    else:

        print("EMPTY")

    T -= 1

   

# Min: -45 45 97 333 653

# Max:  -333 -97 -45 642

# total:  -45 45 333