백준 7662 이중 우선순위 큐

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/7662

풀이

난이도 : Gold IV

일반적으로 우선순위 큐는 max나 min 중 한 가지만 적용할 수 있는 것을 의미하는데, 이 문제는 max와 min을 둘 다 사용할 수 있는 이중 우선순위 큐를 구현하는 문제이다.

이 자료구조는 insert와 delete 기능이 있는데, delete는 최대값과 최솟값 중 선택하여 삭제할 수 있다.

이 문제는 최대값 우선순위 큐와 최소값 우선순위 큐를 사용하여 풀이하였다.

1) min q와 max q를 선언한다. (heapq 사용)
2) 데이터를 입력받으면 두 가지 큐 모두에 값을 넣어주고, 값을 관리하는 dictionary에 데이터에 대한 정보를 저장한다.
3) Insert 명령어가 들어오면 두 큐에 모두 값을 저장하고, dictionary에 정보를 반영한다.
4) Delete 명령어가 들어오면 -1일 경우 최소 큐, 1일 경우 최대 큐에서 값을 삭제한다.
5) 값을 삭제할 때, dictionary에 저장되어 있던 데이터의 수를 -1 카운트하여 반영한다. (이 때, 데이터의 수가 0일 경우 이번 삭제를 무시하고, 큐에서 값을 다시 삭제한다.) -> 반복
6) 마지막에 큐에 있는 값 중 최소값과 최대값을 출력할 때에도 dictionary에서 정보를 확인하고 값을 출력한다.

✔ 주의할 점

• 이 풀이는 백준에서 python3로 제출하면 시간초과 결과가 발생하므로 pypy3로 제출해야 한다.
• 결과를 출력할 때, 만약 큐에 데이터가 하나만 들어있다면 그 값이 최소값이자 최대값이므로 두 번 출력해야 한다.

✔ 잘못된 풀이

• 처음에는 Insert를 할 때, 정보를 저장하는 것이 아니라 Delete를 할 때, 삭제 정보를 저장하도록 구현하였는데, 이렇게 풀이할 경우 delete 정보가 너무 많고 확인해야 할 정보가 많아 시간 초과가 발생하였었다. 이후에 해당 풀이로 변경하여 문제를 해결하였다.

코드

import heapq

t = int(input())

for _ in range(t):
    n = int(input())

    # 최소 우선순위 큐와 최대 우선순위 큐
    min_q = []
    max_q = []

    # insert 된 값들의 정보를 저장할 dictionary
    count = {}

    for _ in range(n):
        a, b = map(str, input().split())

        if a == "I":
            # INSERT : min, max q에 값을 넣어주고, count에 정보 반영
            heapq.heappush(min_q, int(b))
            heapq.heappush(max_q, -int(b))
            if b in count:
                count[b] += 1
            else:
                count[b] = 1
        elif b == "-1":
            # DELETE 최솟값 : min q에 값이 존재한다면 pop, count에 개수 차감 반영
            # 이미 남은 개수가 0개라면 q에서 다시 pop, 남은 개수가 1개 이상이라면 원래숫자-1 반영
            while True:
                if len(min_q) == 0:
                    break
                x = str(heapq.heappop(min_q))
                if count[x] == 0:
                    continue
                else:
                    count[x] -= 1
                    break                
        else:
            # DELTE 최댓값 : 최솟값과 똑같은 방법으로 진행
            while True:
                if len(max_q) == 0:
                    break
                x = str(-heapq.heappop(max_q))
                if count[x] == 0:
                    continue
                else:
                    count[x] -= 1
                    break


    # 결과값을 저장할 list
    results = []

    # min q에 남은 값 중 최솟값을 찾아서 results append (count 반영 포함)
    while True:
        if len(min_q) == 0:
            break
        a = str(heapq.heappop(min_q))
        if count[a] == 0:
            continue
        else:
            count[a] -= 1
            results.append(a)
            break

    # max q에 남은 값 중 최대값을 찾아서 results append (count 반영 포함)
    while True:
        if len(max_q) == 0:
            break
        b = str(-heapq.heappop(max_q))
        if count[b] == 0:
            continue
        else:
            count[b] -= 1
            results.append(b)
            break
    
    # results에 값이 없다면 "EMPTY" 출력, 값이 있다면 있는 값 출력
    if len(results) == 0:
        print("EMPTY")
    elif len(results) == 1:
        # ** 값이 하나라면 최소값과 최대값이 동일하기 때문에 두 번 출력
        print(results[0], results[0])
    else:
        print(results[1], results[0])