[백준] 7662 - 이중 우선순위 큐

1. 문제

7662번: 이중 우선순위 큐

2. 개요

수를 삽입하는 연산과 최댓값, 최솟값을 삭제하는 연산 3가지 기능이 있는 이중 우선순위 큐에 대해 주어진 연산들을 모두 행했을 때, 최종적으로 큐에 남은 최댓값과 최솟값을 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

각 테스트케이스에 대해 최대 힙, 최소 힙, 딕셔너리를 하나씩 만들어둔다.

입력으로 들어오는 값들을 딕셔너리의 key로 등장 횟수를 value로 저장해둔다.

동시에 최대 힙과 최소 힙에 각각 값을 저장한다.

삭제 연산을 진행하면서 딕셔너리의 해당 키의 값을 확인한다.

0 이상이라면 큐 내에 존재한다는 이야기이므로 값을 1씩 감소시키면서 큐에서 빼내준다.

만약 0 이상이 아니라면 이는 이미 다른 곳에서 삭제되어 큐 내에 존재할 수 없는 값이므로 그냥 삭제해 준 뒤 다음 값을 확인한다.

모든 연산을 행한 후 다시 두 큐의 첫 값을 확인하면서 최대, 최소값이 현재 큐에 존재하는 수인지를 확인하고 존재할 수 없는 값이라면 삭제한다.

모든 연산을 마치고 큐의 첫 값 확인까지 마쳤다면 최대 힙과 최소 힙의 첫 값을 답으로 출력한다.

만약 최대 힙이나 최소 힙 둘 중 하나라도 비어있다면 큐가 비어있다는 것이므로 EMPTY를 출력한다.

3-2. Python

import heapq
import sys

T = int(sys.stdin.readline())

for t in range(T):
    k = int(sys.stdin.readline())
    numdict = dict()

    maxheap, minheap = [], []

    for i in range(k):
        command, num = sys.stdin.readline().split()
        num = int(num)

        if command == 'I':
            numdict[num] = numdict.get(num, 0) + 1
            heapq.heappush(minheap, num)
            heapq.heappush(maxheap, -num)

        else:
            if num < 0 and minheap:
                while minheap:
                    if numdict[minheap[0]] > 0:
                        numdict[minheap[0]] -= 1
                        heapq.heappop(minheap)
                        break
                    else:
                        heapq.heappop(minheap)

            elif num > 0 and maxheap:
                while maxheap:
                    if numdict[-maxheap[0]] > 0:
                        numdict[-maxheap[0]] -= 1
                        heapq.heappop(maxheap)
                        break
                    else:
                        heapq.heappop(maxheap)

        while minheap and numdict[minheap[0]] == 0:
            heapq.heappop(minheap)

        while maxheap and numdict[-maxheap[0]] == 0:
            heapq.heappop(maxheap)

    if minheap and maxheap:
        print(-maxheap[0], minheap[0])
    else:
        print("EMPTY")

3-3. C# (통과 실패)

아무리 생각해도 이유를 모르겠다. 반례도 모르겠다.

namespace boj_7662
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());
            Dictionary<int, int> numdict = new Dictionary<int, int>();
            PriorityQueue<int, int> minpq = new PriorityQueue<int, int>();
            PriorityQueue<int, int> maxpq = new PriorityQueue<int, int>();

            for (int t = 0; t < T; t++)
            {
                int k = int.Parse(Console.ReadLine());
                numdict.Clear();
                minpq.Clear();
                maxpq.Clear();

                for (int i = 0; i < k; i++)
                {
                    string[] commands = Console.ReadLine().Split();
                    string command = commands[0];
                    int num = int.Parse(commands[1]);

                    if (command == "I")
                    {
                        if (numdict.ContainsKey(num))
                            numdict[num]++;

                        else
                            numdict[num] = 1;

                        minpq.Enqueue(num, num);
                        maxpq.Enqueue(num, -num);
                    }

                    else
                    {
                        if (num < 0 && minpq.Count > 0)
                        {
                            while (minpq.Count > 0)
                            {
                                if (numdict[minpq.Peek()] > 0)
                                {
                                    numdict[minpq.Peek()]--;
                                    minpq.Dequeue();
                                    break;
                                }

                                else
                                    minpq.Dequeue();
                            }
                        }

                        else if (num > 0 && maxpq.Count > 0)
                        {
                            while (maxpq.Count > 0)
                            {
                                if (numdict[maxpq.Peek()] > 0)
                                {
                                    numdict[maxpq.Peek()]--;
                                    maxpq.Dequeue();
                                    break;
                                }

                                else
                                    maxpq.Dequeue();
                            }
                        }
                    }

                    while (minpq.Count > 0 && numdict[minpq.Peek()] == 0)
                        minpq.Dequeue();

                    while (maxpq.Count > 0 && numdict[maxpq.Peek()] == 0)
                        maxpq.Dequeue();
                }

                if (minpq.Count > 0 && maxpq.Count > 0)
                    Console.WriteLine($"{maxpq.Peek()} {minpq.Peek()}");

                else
                    Console.WriteLine("EMPTY");
            }
        }
    }
}