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

이 문제는 multiset을 이용해서 풀었다.

 

문제 제목대로 진짜 우선순위 큐 두 개 만들어서 하면 시간 초과가 난다.

문제에서 중복된 숫자가 들어올 수 있기 때문에 set이 아닌 multiset을 사용했다.

set, multiset은 기본적으로 오름차순 정렬이 되어있기 때문에 문제의 요구사항을 쉽게 해결할 수 있다.

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

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

	int T;
	cin >> T;
	for (int test = 0; test < T; test++) {
		int k;
		cin >> k;

		multiset<int> numbers;

		for (int command = 0; command < k; command++) {
			char c;
			int n;
			cin >> c >> n;

			if (c == 'D') {
				// delete
				if (numbers.empty()) {
					continue;
				}

				if (n == 1) {
					// max delete
					numbers.erase(--numbers.end());
				} else {
					// min delete
					numbers.erase(numbers.begin());
				}
			} else {
				// insert
				numbers.insert(n);
			}
		}

		if (numbers.empty()) {
			cout << "EMPTY" << '\n';
		} else {
			auto start = numbers.begin();
			auto end = --numbers.end();
			cout << *end << " " << *start << '\n';
		}
	}

	return 0;
}