문제 링크

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

문제 설명

• I, N이 주어지면 N 삽입
• D, 1이 주어지면 최댓값 삭제
• D, -1이 주어지면 최솟값 삭제
• 연산 후 최댓값, 최솟값 출력

풀이

• heapq로 최대힙, 최소힙을 만든다

• I, N일 때

  • 양쪽에 모두 삽입
  • dict에 count += 1

• D, 1일 때

  • 최대 힙에서만 삭제
  • dict에 count -= 1

• D, -1일 때

  • 최소 힙에서만 삭제
  • dict에 count -= 1

삭제 구현 방법

• pop
• pop으로 나온 노드가 count > 0 일 경우 count -= 1 후 종료 (이미 삭제된 노드인지 판별)
• 아닐 경우 반복
• 만약 count == 0일 경우 dict에서 key를 제거 (이후 최대 최소를 탐색하지 않기 위해)

코드

import sys, heapq
ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
    k = int(ipt())
    max_h, min_h = [], []
    count_dict = dict()
    for _ in range(k):
        op, n = ipt().split()
        n = int(n)
        if op == 'I':
            if n in count_dict:
                count_dict[n] += 1
            else:
                count_dict[n] = 1
            heapq.heappush(min_h, n)
            heapq.heappush(max_h, -n)
        elif op == 'D':
            if n == 1:
                while max_h:
                    c = -heapq.heappop(max_h)
                    if c in count_dict and count_dict[c] > 0:
                        count_dict[c] -= 1
                        if not count_dict[c]: 
                            del count_dict[c]
                        break
            else:
                while min_h:
                    c = heapq.heappop(min_h)
                    if c in count_dict and count_dict[c] > 0:
                        count_dict[c] -= 1
                        if not count_dict[c]: 
                            del count_dict[c]
                        break
    if count_dict:
        sorted_items = sorted(count_dict.items())
        opt(f'{sorted_items[-1][0]} {sorted_items[0][0]}\n')
    else:
        opt('EMPTY\n')