[BOJ] 7662. 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

문제: 최댓값과 최솟값을 뺄 수 있는 이중 우선 순위 큐를 만들어라

 

문제 이해하기!!

이중 우선 순위 큐면 사실 deque을 이용해서 뒤에서 빼고 앞에서 빼면 되지만,

이 문제에서는 insert까지 생각해야 합니다.

그러므로 새로운 방식으로 짜야하는데요,

그 방법은 최소, 최대 힙 두개를 사용한 방법입니다.

 

제가 푼 방식을 설명하자면,

1. 최소 최대 힙을 이용하여 각 Insert마다 숫자를 받고, 해당 숫자를 dictionary에 갯수를 셉니다.

2. Delete마다 pop을 하는데, 각 최소, 최대 힙에는 이미 없어진 숫자가 있으므로 dictionary의 각 숫자 갯수를 확인하여야 합니다. 

3. 1, 2번이 끝나면 딕셔너리에 있는 숫자 중, 갯수가 1개 이상인 수를 저장하고 제일 큰 수와 제일 작은 수를 출력합니다.

plus. 이 때, 숫자가 여러개 있는 것을 중요하지 않습니다. 큰 수, 작은 수를 하나씩 출력하기 때문입니다.

 

코드:

import heapq
from collections import defaultdict
from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    min_arr = []
    max_arr = []
    dic = defaultdict(int)
    cnt = 0
    for i in range(N):
        cmd, num = input().rstrip().split()
        if cmd == "I":
            cnt += 1
            dic[int(num)] += 1
            heapq.heappush(min_arr, int(num))
            heapq.heappush(max_arr, -int(num))
        else:
            if num == "1":
                while max_arr:
                    key = -heapq.heappop(max_arr)
                    if dic.get(key):
                        dic[key] -= 1
                        break
            else:
                while min_arr:
                    key = heapq.heappop(min_arr)
                    if dic.get(key):
                        dic[key] -= 1
                        break

    ans = [key for key, value in dic.items() if value > 0]
    if ans:
        ans.sort()
        print(ans[-1], ans[0])
    else:
        print("EMPTY")