🖊️ 문제

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

---

🖊️ 풀이

보자마자 훼이크에 당했당.
이중 우선순위 큐를 구하라길래,,
당연히 maxQueue, minQueue를 놓고 두 Queue를 이어주는 unordered_map을 사용했는데,
하다가 실패했다.

뭐 그렇게 해도 풀리긴 하겠지만 너무 복잡한거 ㅠㅠ 그리고 너무너무 비효율적이다..

근데 여기서 필요한 자료구조는
1. 항상 정렬 유지
2. 중복 가능
3. 앞, 뒤 요소 모두에 접근 가능

해야 하므로,
multiset을 사용할 수 있다.

그래서 multiset을 사용하였고,
이걸 사용하니 너무 쉽게 풀린 문제

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

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

	int T;
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		multiset<int> ms;
		
		int k;
		cin >> k;

		for (int j = 0; j < k; j++) {
			char order;
			int n;
			cin >> order >> n;

			if (order == 'I') ms.insert(n);
			else if (ms.empty()) continue;
			else if (n == 1) ms.erase(--ms.end());
			else if (n == -1) ms.erase(ms.begin());
		}
		if (ms.empty()) cout << "EMPTY\n";
		else cout << *--ms.end() << " " << *ms.begin() << '\n';
	}
}