#BOJ7662

새해 목표

늘 그렇듯 새해 목표는 거창해야 하니깐 올해는 365일 백준을 매일매일 풀면서 벨로그도 매일 한 개씩 남겨보려고 한다. 백준에 대한 벨로그로 매일 남기는 것은 불가능에 가까울 것 같아서... 다른 분야로도 조금 남겨보려고 한다. 그래도 첫 날이니까 많이 까먹은 분야부터 다뤄보기로 했다.

이중 우선순위 큐

문제를 보고 나서 양 끝단에서 출력해주는 문제이니 그냥 Priority Queue를 두 개 만들까 했다. 하지만 한 가지 간과한 부분이 그렇게 되면 연산 과정중에 옳지 않은 값이 나올 경우의 수가 너무 쉽게 발견 되었다. 그래서 과감하게 큐를 버리고 힙큐를 사용하기로 하였다. Heap자체가 최댓값과 최솟값을 빠르게 찾기 위해서 고안된 연산이니 이를 활용해서 문항을 해결하면 해결 가능할 것이라고 생각했다. 다만, Priority Queue를 사용하는 부분이랑 같은 문제점이 발생하였는데 바로 동기화 문제였다. 동기화 문제를 해결하기 위해서 어떤 방식을 사용할까 고민을 많이 하였다. 그러기 위해서 유지되는 값에는 어떤 것이 있을 까 고민하였고, deleted라는 딕셔너리를 만들어서 사용하였다. 그 외의 과정은 단순한 heapq과정과 유사하니 생략하겠다 아래는 코드와 주석이다. 코드가 너무 더러운것은 아닌지 걱정이 된다. 주석은 우리 위대하신 GPT형님의 도움을 받았다.

import heapq
import sys
from collections import defaultdict

def sync_heaps(max_heap, min_heap, exists):
   """
   Max heap과 Min heap을 동기화하는 함수입니다.
   삭제된 원소를 추적하고, 두 힙에서 해당 원소를 제거합니다.
   """
   # Max heap에서 삭제될 원소가 있는지 확인하고 삭제합니다.
   while max_heap and not exists[max_heap[0][1]]:
       heapq.heappop(max_heap)

   # Min heap에서 삭제될 원소가 있는지 확인하고 삭제합니다.
   while min_heap and not exists[min_heap[0][1]]:
       heapq.heappop(min_heap)

def solution(operations):
   """
   주어진 연산을 수행하고, 이중 우선순위 큐에서 최댓값과 최솟값을 반환합니다.
   """
   max_heap, min_heap = [], []  # Max heap과 Min heap 초기화
   exists = defaultdict(bool)   # 원소의 존재 여부를 추적하기 위한 defaultdict
   count = 0  # 각 원소에 부여할 고유 인덱스

   for op in operations:
       operation, num = op[0], int(op[2:])
       if operation == "I":
           # 'I' 연산은 원소를 삽입합니다.
           heapq.heappush(max_heap, (-num, count))
           heapq.heappush(min_heap, (num, count))
           exists[count] = True
           count += 1
       elif operation == "D":
           # 'D' 연산은 원소를 삭제합니다.
           if num == 1 and max_heap:
               # 최댓값 삭제
               exists[max_heap[0][1]] = False
               heapq.heappop(max_heap)
           elif num == -1 and min_heap:
               # 최솟값 삭제
               exists[min_heap[0][1]] = False
               heapq.heappop(min_heap)
           sync_heaps(max_heap, min_heap, exists)

   sync_heaps(max_heap, min_heap, exists)

   # 결과 반환
   if not max_heap or not min_heap:
       return "EMPTY"  # 큐가 비어있으면 'EMPTY' 반환
   else:
       return f"{-max_heap[0][0]} {min_heap[0][0]}"  # 큐에 원소가 있으면 최댓값과 최솟값 반환

# 테스트 케이스
T = int(sys.stdin.readline())  # 테스트 케이스의 수 T
for _ in range(T):
   k = int(sys.stdin.readline())  # 각 테스트 케이스별 연산의 개수 k
   operations = [sys.stdin.readline().rstrip() for _ in range(k)]  # 연산들을 입력받음
   print(solution(operations))  # 솔루션 함수 호출 및 결과 출력