BOJ 7662 이중 우선순위 큐

기본적으로 우선순위 큐는 삽입,삭제에 대해 O(logN)의 시간복잡도를 가진다. 또한 트리구조를 취하는 MaxHeap( 또는 MinHeap)으로 구현된다.

 

문제에서 Q의 종류중 D 1 은 가장 큰 값 삭제, D -1은 가장 작은 값 삭제를 수행하야 하지만 우선순위 큐 한개로는 불가능 하다. 따라서 MaxHeap, MinHeap으로 구현된 우선순위 큐 2개를 사용해야 한다. 

 

여기 까지가 처음 생각한 방법이다. 하지만 문제는 두 큐가 동기화가 되지 않는다는 점이다.  

한참을 고민하던도중 multiset이라는 자료구조를 이용하면 해결 가능하다는 것을 발견하였다. 

 

multiset이란 기본적인 set은 중복을 포함하지 않고 정렬되어있지만  multiset은 중복을 허용한 정렬된 자료구조이다. 또한 특정 값을 erase라는 메서드를 통해 쉽게 지울수 있다. 기본적으로 erase는 파라미터로 keyval을 갖는다. 이는 해당 set에서 특정 값을 모두 지우는 메서드이다. 하지만 한개의 값만 지우기 위해 iterator또한 파라미터로 전달할 수 있다. 

 

이를 이용한 풀이는 다음과 같다.

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;

void solution()
{
	int k;
	cin >> k;

	multiset<int> ms;

	for(int i = 0; i < k; i++)
	{
		char c;
		int num;

		cin >> c >> num;

		if(c == 'I')
		{
			ms.insert(num);
		}

		if(c == 'D')
		{
			if(num == 1)
			{
				if(!ms.empty())
				{
					multiset<int>::iterator it = ms.find(*--ms.end());
					ms.erase(it);
				}	
			}
			else
			{
				if(!ms.empty())
				{
					multiset<int>::iterator it = ms.find(*ms.begin());
					ms.erase(it);
				}
			}
		}
	}

	if(ms.empty())
	{
		cout << "EMPTY";
	}
	else
	{
		cout << *--ms.end() << " " << *ms.begin();
	}
}

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

	int t;
	cin >> t;

	while(t > 0)
	{
		solution();
		cout << "\n";
		t--;
	}
}