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

 

 

아이디어

 

최솟값을 찾는 우선순위 큐, 최댓값을 찾는 우선순위 큐, 남은 값의 개수를 저장하는 딕셔너리를 사용하여 해결한다.

 

 

풀이

 

우선순위 큐를 사용하기 위해 heapq 모듈의 heappush와 heappop을 불러온다.

최댓값을 저장하는 우선순위 큐 max_heap과 최솟값을 저장하는 우선순위 큐 min_heap을 생성하고,

남은 데이터의 총 개수 total, 남은 값의 개수를 저장하는 딕셔너리 cnt_dict를 생성한다.

 

k번의 for문에서 연산이 I이면 cnt_dict를 참고해 추가하려는 값의 남은 개수가 0이면 min_heap과 max_heap에 추가하고,

그렇지 않으면 두 우선순위 큐에 추가하지 않고 cnt_dict의 값과 total을 1 증가시킨다.

연산이 D이면 cnt_dict를 참고해 남은 개수가 0인 max_heap의 최댓값 또는 min_heap의 최솟값을 제거하고,

cnt_dict의 값과 total을 1 감소시키고, 해당 값이 더 이상 없다면 각각 max_heap과 min_heap에서 제거한다.

 

마지막 total의 값이 0보다 크다면 남은 개수가 1 이상인 max_heap의 최댓값과 min_heap의 최솟값을 출력하고,

그렇지 않으면 EMPTY 문자열을 출력한다.

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

def solution():
    T = int(input())
    for t in range(T):
        max_heap = []
        min_heap = []
        total = 0
        cnt_dict = dict()
        k = int(input())
        for _ in range(k):
            cmd = input().split()
            cmd[1] = int(cmd[1])
            if cmd[0] == 'I':
                cnt = cnt_dict.get(cmd[1], 0)
                if cnt == 0:
                    heappush(max_heap, -cmd[1])
                    heappush(min_heap, cmd[1])
                cnt_dict[cmd[1]] = cnt+1
                total += 1
            elif total > 0:
                if cmd[1] > 0:
                    while cnt_dict.get(-max_heap[0], 0) == 0:
                        heappop(max_heap)
                    cnt = cnt_dict.get(-max_heap[0], 0)
                    cnt_dict[-max_heap[0]] = cnt-1
                    if cnt == 1:
                        heappop(max_heap)
                    total -= 1
                elif cmd[1] < 0:
                    while cnt_dict.get(min_heap[0], 0) == 0:
                        heappop(min_heap)
                    cnt = cnt_dict.get(min_heap[0], 0)
                    cnt_dict[min_heap[0]] = cnt-1
                    if cnt == 1:
                        heappop(min_heap)
                    total -= 1
        if total > 0:
            while cnt_dict.get(-max_heap[0], 0) == 0:
                heappop(max_heap)
            while cnt_dict.get(min_heap[0], 0) == 0:
                heappop(min_heap)
            print(-max_heap[0], min_heap[0])
        else:
            print('EMPTY')

solution()