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

이 문제는 우선순위 큐를 2개를 놓고 한 쪽은 최대힙, 다른 쪽은 최소힙을 구성하도록 하고 적절히 입력과 삭제를 반복하면 풀리는 문제이다.

하지만, C++에서는 더 쉽게 푸는 방법이 있어 포스팅해본다.

C++ STL의 set은 이진 탐색 트리 중 하나인 red-black트리로 이루어진 자료구조이므로, 내부적으로 원소들을 정렬된 순서로 방문하기 용이하다.

최소값은 begin()에, 최대값은 prev(end())에 존재하므로 손쉽게 최대와 최소값을 삭제할 수 있다.

set의 삽입, 삭제, 접근, 수정 등의 대부분의 연산은 O(logN)으로 상당히 빠르다.

하지만, 이 문제에서는 중복된 값이 입력될 수 있기 때문에, multiset을 이용해 풀면 된다.

#include <bits/stdc++.h>
using namespace std;

int tc;

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

	cin >> tc;
	while (tc--) {
		int k, n;
		char c;
		multiset<int> s;

		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> c >> n;
			if (c == 'I') s.insert(n);
			else if (s.empty()) continue;
			else if (n < 0) s.erase(s.begin());
			else s.erase(prev(s.end()));
		}

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