[ 7662 ] [ heap ] 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

---

풀이 과정

---

1. 최소히프, 최대히프를 만들어 두고, 실제 데이터 개수를 체크할 딕셔너리를 하나 만들어 둔다.
2. 데이터 삽입
   1. 데이터를 최소히프, 최대히프에 모두 삽입
   2. 딕셔너리 내 해당 데이터 개수를 1개 증가시켜 준다.
3. 데이터 삭제
   1. 최소값을 뽑아야 하면 최소히프에서 빼준다.
   2. 최댓값을 뽑아야 하면 최대히프에서 빼준다.
   3. 단, (1), (2) 과정에서 뽑은 데이터에 대응되는 데이터 개수가 0개인 경우에는 이미 다른 히프에서 빼준 것이므로, 다시 빼주어야 한다.
4. 마지막에 큐가 비어있다면 Empty를, 비어있지 않다면 최댓값, 최솟값을 출력한다.
   
   1. 각각 최대히프, 최소히프에서 빼주고, 만약 빼줄 데이터가 없는 경우에는 Empty를 출력시켜주면 된다.

---

소스 코드

---

import heapq
import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T): 
    min_heap = []
    max_heap = []
    element_dict = defaultdict(lambda: 0)
    K = int(input())
    for __ in range(K):
        cmd, data = input().split()
        data = int(data)
        if cmd == 'I':
            heapq.heappush(min_heap, data)
            heapq.heappush(max_heap, -data)
            element_dict[data] += 1
        if cmd == 'D':
            if data == -1:
                while min_heap:
                    r = heapq.heappop(min_heap)
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
            else:
                while max_heap:
                    r = heapq.heappop(max_heap)
                    r = -r
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
    min_value = None
    max_value = None
    while min_heap:
        r = heapq.heappop(min_heap)
        if element_dict[r] > 0:
            min_value = r
            break
            
    while max_heap:
        r = heapq.heappop(max_heap)
        r = -r
        if element_dict[r] > 0:
            max_value = r
            break
    if min_value == None:
        print('EMPTY')
    else:
        print(max_value, min_value)