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

7662번: 이중 우선순위 큐

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

unordered_map<int, int> CheckNum;
priority_queue<int> MaxHeap;
priority_queue<int, vector<int>, greater<int>> MinHeap;

void Input(int Number)
{
	++CheckNum[Number];
	MaxHeap.emplace(Number);
	MinHeap.emplace(Number);
}

void DeleteMax()
{
	if (!MaxHeap.empty())
	{
		int Number = MaxHeap.top();
		MaxHeap.pop();
		--CheckNum[Number];
	}
}

void DeleteMin()
{
	if (!MinHeap.empty())
	{
		int Number = MinHeap.top();
		MinHeap.pop();
		--CheckNum[Number];
	}
}

void CleanHeap()
{
	while (!MaxHeap.empty()
		&& CheckNum[MaxHeap.top()] == 0)
	{
		MaxHeap.pop();
	}

	while (!MinHeap.empty()
		&& CheckNum[MinHeap.top()] == 0)
	{
		MinHeap.pop();
	}
}

void Test()
{
	CheckNum.clear();
	while (!MaxHeap.empty())
	{
		MaxHeap.pop();
	}
	while (!MinHeap.empty())
	{
		MinHeap.pop();
	}

	int K;
	cin >> K;
	for (int i = 0; i < K; ++i)
	{
		char Command;
		int Number;
		cin >> Command >> Number;

		if (Command == 'I')
		{
			Input(Number);
		}
		else if (Command == 'D' && Number == 1)
		{
			DeleteMax();
			CleanHeap();
		}
		else if (Command == 'D' && Number == -1)
		{
			DeleteMin();
			CleanHeap();
		}
	}

	if (MaxHeap.empty() || MinHeap.empty())
	{
		cout << "EMPTY\n";
		return;
	}

	cout << MaxHeap.top() << ' ' << MinHeap.top() << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		Test();
	}
}

---

 

우선순위 큐 두 개와 해시 맵 한 개를 이용해서 풀었습니다.

주어진 입력에 따라서 MaxHeap과 MinHeap으로 pop 연산을 따로 수행하도록 하고

unordered_map에 각 숫자 데이터가 몇 개 남아있는지를 저장하도록 했습니다.

삭제 연산을 수행하고나면 해시맵에 남아있는 데이터를 파악해서 양쪽 힙의 데이터를 정리하도록 하는 부분이 중요했습니다.