[백준/Python]7662: 이중 우선순위 큐

문제

https://www.acmicpc.net/problem/7662
백준 문제집 - 0x16강 - 이진 검색 트리

 

알고리즘: 우선순위 큐

---

풀이

 

단순하게 최대힙, 최소힙으로만 관리했다가 틀렸던 문제다.
최대힙에서 추출했던 숫자가 최소힙에서는 아직 존재할수도 있으므로, 각 숫자의 상태(갯수)를 따로 저장해둬야한다.

 

1. 입력이 I로 주어질경우 해당 숫자의 갯수를 +1 카운트.
2. D일경우 명령어에 맞춰 최대/최소힙에서 숫자를 추출.
   • 만약 추출한 숫자의 갯수가 0인 상태라면 이미 전체 힙에서 제거된 상태이므로, 갯수가 0이 아닌 숫자를 찾을때까지 계속 추출한다.
   • 찾으면 1 감소시킨 후 해당 숫자를 출력하면 된다.

 

모든 과정이 끝나고나서 힙의 길이가 0이라면 "EMPTY"를, 남아있다면 최댓값, 최솟값을 추출한다.
이때는 숫자의 갯수를 감소시키지 않는다.
힙의 길이가 1일때의 최댓값, 최솟값은 동일하기 때문이다.

 

그리고 D 연산(추출)은 힙이 비어있을때도 들어올 수 있다.
방법은 여러가진데 나는 length로 힙의 길이를 따로 저장해뒀다.
I일경우 length += 1, D일경우 최대/최소를 막론하고 length -= 1을 실행한다.
입력이 D일때 length = 0이라면 그대로 넘어가주면 된다.

 

전체 코드

# 메모리: 181816KB / 시간: 3860ms
from sys import stdin
from heapq import heappush, heappop


input = stdin.readline

def solution():
    k = int(input())
    L, S = [], []  # L: 최대힙, S: 최소힙
    length = 0
    status = {}  # 숫자들의 상태(갯수)를 저장할 딕셔너리

    for _ in range(k):
        cmd, num = input().rstrip().split()
        num = int(num)

        if cmd == "I":
            heappush(L, -num)
            heappush(S, num)
            length += 1
            status[num] = status.get(num, 0) + 1
        else:
            if length <= 0:
                continue
            if num == 1:
                # 만약 숫자의 갯수가 0이라면 이미 힙에서 추출했다는 뜻이므로,
                # 아직 추출되지 않은 숫자를 찾을때까지 pop
                while True:
                    n = -heappop(L)
                    if status[n] > 0:
                        status[n] -= 1
                        break
            else:
                while True:
                    n = heappop(S)
                    if status[n] > 0:
                        status[n] -= 1
                        break
            length -= 1

    # 길이가 0이라면 "EMPTY" 반환
    if length <= 0:
        return "EMPTY"

    # 아니라면 0이 아닌 숫자 중 최대, 최소값 반환
    while True:
        _max = -heappop(L)
        if status[_max] > 0:
            break

    while True:
        _min = heappop(S)
        if status[_min] > 0:
            break

    return f"{_max} {_min}"


for _ in range(int(input())):
    print(solution())