[BOJ] 7662번 이중 우선순위 큐 (C++)

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

7662번: 이중 우선순위 큐

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, k, num;
	char c;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		multiset<int> ms;
		cin >> k;
		for(int j = 0; j < k; j++){
			cin >> c;
			if(c == 'I'){
				cin >> num;
				ms.insert(num);
			} else if(c == 'D'){
				cin >> num;
				if(ms.empty()) continue;
				if(num == -1) ms.erase(ms.begin());
				else if(num == 1) {
					auto it = ms.end();
					it--;
					ms.erase(it);
				}
			}
		}
		if(ms.empty()) cout << "EMPTY" << '\n';
		else {
			auto it = ms.end();
			it--;
			cout << *it << " " << *ms.begin() << '\n';
		}
	}
	return 0;
}

multiset을 사용하여 쉽게 풀 수 있는 문제이다. multiset에 원소를 넣으면 자동으로 오름차순 정렬된다.

 

최대값을 pop할 때는 end() 함수를 통해 끝 값에 접근하여 erase() 함수를 통해 해당 주소의 값을 지운다. 주의할 점은 end() 함수가 가장 끝 값의 다음 주소값을 가리키기 때문에 반복자에서 1을 빼주어야 한다. 

최소값을 pop할 때도 begin()을 통해 최소값의 주소에 접근하고 erase() 함수를 사용한다.