[BOJ] 이중 우선순위 큐 (7662, G4)

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

 

 

 

 

이게 무슨 골4야... 골1~2줘도 될거 같은데

힙 하나에서 최댓값과, 최솟값을 모두 뺄 수 있을까?

기본적으로 파이썬의 힙에서는 최솟값만 빼게 되어있다. 최댓값을 빼는 힙은 모든 원소를 -1배해서 넣고 pop한 원소를 다시 돌려줘야 한다. 

문제는 이걸 하고 싶다고, 최솟값을 만든 힙에다가 원소를 -1배 하면, 힙의 구조가 다 깨진다! 힙에서는 힙 명령어인 push, pop, 루트 확인만 고려해야 한다. (애초에 사실 자료구조 이론상, 삽입/삭제도 맘대로 하는게 아니었다. 별도의 절차와 알고리즘 순서가 있었다.)

따라서 이 경우에는 두 개의 힙을 만들어야 한다. 최대힙과, 최소힙.
문제는 최대힙에서 뺄 때, 최소힙은 그 원소를 어떻게 빼야하는가? 이다. 사실 위의 이론만 생각해서는 물리적으로 뺄 수 없다.

즉 무슨 원소가 빠졌는지를 기억해 내야 하는데, 심지어 하나의 원소가 여러개 들어올 수 있고 최대인지, 최소인지 뭔질 모른다.
이 때, dict를 활용한다. 들어온 원소의 개수를 모두 기억하자. 원소를 push 하면 개수 추가, pop 하면 감소. 그러다가 0개가 되면 애초에 dict에 제거 해야 한다.  이걸 조금 더 고려하면, heap에서 원소를 빼려는데 애초에 dict에 없는 원소를 빼려고 한다면 잘못 뺀 거니까, dict에 있는 원소만 빼게 해야 한다.

import heapq
import sys
input = sys.stdin.readline

t_case = int(input())
for _ in range(t_case):
    min_heap = []
    max_heap = []
    heapq.heapify(min_heap)
    heapq.heapify(max_heap)
    # 큐를 두개로 분할했지만, 실제로는 1개인 것처럼 운영해야 한다.
    
    num_counter = {}
    
    num_order = int(input())
    for _ in range(num_order):
        cur_ord_str = list(map(str, input().split()))
        cur_ord = cur_ord_str[0]
        cur_num = int(cur_ord_str[1])
        
        if cur_ord == "I":
            heapq.heappush(min_heap, cur_num)
            heapq.heappush(max_heap, -cur_num)
            if cur_num not in num_counter:
                num_counter[cur_num] = 1
            else:
                num_counter[cur_num] += 1
        else:
            # 최솟값 삭제
            if cur_num == -1:
                # step 1. 그게 실제로 존재하는 최솟값인가 이미 없어야 했던 애면 제거
                while min_heap and min_heap[0] not in num_counter:
                    heapq.heappop(min_heap)
                # step 2. 실제 최솟값을 제거한다.
                if min_heap:
                    cur_min = min_heap[0]
                    num_counter[cur_min] -= 1
                    if num_counter[cur_min] == 0:
                        del num_counter[cur_min]
                    heapq.heappop(min_heap)
            else:
                # step 1. 그게 실제로 존재하는 최댓값인가, 이미 없어야 했던 애면 제거
                while max_heap and -max_heap[0] not in num_counter:
                    heapq.heappop(max_heap)
                # step 2. 실제 최댓값을 제거한다. 음수에 주의
                if max_heap:
                    cur_max = -max_heap[0]
                    num_counter[cur_max] -= 1
                    if num_counter[cur_max] == 0:
                        del num_counter[cur_max]
                    heapq.heappop(max_heap)
    # 마지막으로 쓰레기 값 제거
    while min_heap and min_heap[0] not in num_counter:
        heapq.heappop(min_heap)
    while max_heap and -max_heap[0] not in num_counter:
        heapq.heappop(max_heap)
    # 최종 정답 출력, dict 확인
    empty_flag = True
    for cur_num in num_counter:
        if num_counter[cur_num] > 0:
            empty_flag = False
            break
        
    if empty_flag:
        print("EMPTY")
    else:
        print("%d %d" %(-max_heap[0], min_heap[0]))