백준 7662번: 이중 우선순위 큐 (C++)

https://www.acmicpc.net/submit/7662

우선 해당 문제는 바킹독님 강의를 참고하여 이진 검색 트리 알고리즘을 활용한 STL인 multiset을 활용하였다. 이 문제는 Key, value 대응 관계가 필요한건 아니니 map보다는 set이나 multiset(중복허용)이 적합하다. (최솟값 삭제 최댓값 삭제 모두 O(logN))

#include <bits/stdc++.h>
#include <set>

using namespace std;




int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int k;
		cin >> k;
		multiset<int> ms;
		while(k--)
		{
			char c; 
			cin >> c;

			
			
			if (c == 'D')
			{
				int num;
				cin >> num;
				if (ms.empty()) continue;
				if (num == 1)
				{
					ms.erase(prev(ms.end()));
				}
				else if (num == -1)
				{
					ms.erase(ms.begin());
				}
			}
			else
			{
				int num;
				cin >> num;
				ms.insert(num);
			}
			
		}

		if (ms.empty())
		{
			cout << "EMPTY" << '\n';
		}
		else
		{
			cout << *prev(ms.end()) << ' ' << *(ms.begin()) << '\n';
		}
	}
}