[백준] 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')

좋은 웹페이지 즐겨찾기