백준 7662 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

이 문제는 한동안 다른프로젝트를 진행하다가 다시 알고리즘을 풀면서 우선순위 큐에 대해 공부해야할 필요성이 있을거 같아 풀기 시작한 문제이다 이 문제의 경우 처음에 이중 우선순위 큐라는 자료구조를 직접 클래스로 작성할 까 생각하다가 메모리제한과 시간제한이 여유로운 것을 보고 최대값 우선순위 큐와 최솟값 우선순위 큐를 2개를 사용하여 풀면 될 것 같은 생각을 했다 이에 그렇게 구현 하여 작성했

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pqMin;
priority_queue<int, vector<int>> pqMax;
map<int, int>cnt;
void insertpq(int n) {
	pqMax.push(n);
	pqMin.push(n);
	cnt[n]++;
}
void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

int main() {

	int T, n, k;
	char mode;
	cin >> T;
	for (int i = 0; i < T; i++) {
		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

		cnt.clear();

		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> mode >> n;
			if (mode == 'I') {
				insertpq(n);
			}
			else {
				if (n == 1)
					deleteMax();
				else
					deleteMin();
				while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
					pqMax.pop();
				}
				while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
					pqMin.pop();
				}
			}
		}
		if (pqMax.empty() || pqMin.empty()) {
			cout << "EMPTY\n";
		}
		else cout << pqMax.top() << " " << pqMin.top() << '\n';
	}
	return 0;
}

이문제의 경우 가장 중요한건  최솟값 우선순위 큐와 최댓값 우선순위 큐를 계속 동기화를 시켜줘야 한다 즉 최댓값 우선순위 큐에서 삭제한 데이터는 후에 최솟값 우선순위 큐에서도 삭제를 해줘야한다. 또한 이 문제의 경우 여러개의 테스트 케이스를 한번에 입력함으로 각각의 테스트 케이스 마다 우선순위 큐를 초기화 시켜줘야한다 이에

		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

이 부분을 작성해서 매 테스트 케이스 마다 초기화 시켜주었다 그후 2번째로 중요한 부분은

void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

이 두 부분이다 이 두부부느이 경우 각자의 우선순위 큐에서 데이터를 지울때 일차적으로 데이터를 동기화 시켜주기 위함이다 만약 어느 한쪽에서의 값을 지웠을 경우 cnt의 값이 0이되있을 것이므로 반대쪽에 큐에서 cnt가 0인 부분들을 pop해줄수 있게 하기위해서다