[Gold 4] 7662번 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

이 문제는 우선순위 큐를 사용해서 해결할 수 있다.

 

알고리즘은 다음과 같다.

1. 내림차순과 오름차순으로 정렬해주는 우선순위 큐를 선언한다. 큐의 요소는 값과 삽입 순서를 넣는다.
   • 우선순위 큐 생성 방법
     • priority_queue<자료형, 구현체, 비교연산자>
     • 비교 연산자에는 less<자료형>과 greater<자료형>이 있다.
     • 자료형에 pair를 사용하는 경우 정렬 시 첫번째 값을 통해 먼저 정렬하고, 값이 같을 경우 두번째 값을 통해 정렬
     • 구현체는 우선순위큐를 생성할 때 사용할 컨테이너를 의미한다.
2.  I 명령이 들어오면 최소큐와 최대큐에 값을 삽입하고, 현재 삽입 순서를 check 한다.
3. D 명령이 들어오면 -1인 경우와 1인 경우로 나뉘게 된다.
   • -1 명령인 경우
     • 최소큐가 비어있지 않을 때 까지 check를 통해 큐의 top이 버리지 않은 값인지 확인. 이때 큐의 요소를 버리면서 순회
     • 순회가 끝나고 최소큐가 비어있지 않는다면, 순회가 끝날 때의 삽입 순서를 uncheck 한다.
     • 이 과정은 최소큐와 최대큐를 동기화 하기 위한 과정
   • 1 명령인 경우
     • 촤대큐가 비어있지 않을 때 까지 check를 통해 큐의 top이 버리지 않은 값인지 확인. 이때 큐의 요소를 버리면서 순회
     • 순회가 끝나고 최대큐가 비어있지 않는다면, 순회가 끝날 때의 삽입 순서를 uncheck 한다.
     • 이 과정은 최소큐와 최대큐를 동기화 하기 위한 과정
4. 명령을 마쳤다면, 최소 큐가와 최대 큐가 비어있지 않을 때 까지 큐의 top이 버리지 않은 값인지 확인
5. 최소 큐와 최대 큐가 모두 비어있다면 EMPTY 출력
6. 비어있지 않았다면 최대 큐의 탑과 최소 큐의 탑을 출력

 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int T, N;
int check[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		priority_queue<pair<int, int>> max_q;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_q;
		for (int i = 0; i < N; i++) {
			char order;
			int num;
			cin >> order >> num;
			if (order == 'I') {
				max_q.push(make_pair(num, i));
				min_q.push(make_pair(num, i));
				check[i] = 1;
			}
			else if (order == 'D') {
				if (num == -1) {
					while (!min_q.empty()) {
						int X = min_q.top().second;
						if (check[X] == 1) break;
						min_q.pop();
					}
					if (min_q.size() > 0) {
						int X = min_q.top().second;
						check[X] = 0;
					}
				}
				else {
					while (!max_q.empty()) {
						int X = max_q.top().second;
						if (check[X] == 1) break;
						max_q.pop();
					}
					if (max_q.size() > 0) {
						int X = max_q.top().second;
						check[X] = 0;
					}
				}
			}
		}
		while (!min_q.empty()) {
			int X = min_q.top().second;
			if (check[X] == 1) break;
			min_q.pop();
		}
		while (!max_q.empty()) {
			int X = max_q.top().second;
			if (check[X] == 1) break;
			max_q.pop();
		}
		if (max_q.empty() && min_q.empty()) cout << "EMPTY" << "\n";
		else cout << max_q.top().first << " " << min_q.top().first << "\n";
	}
	return 0;
}