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

문제 링크입니다. https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

우선순위 큐를 이용하는 문제입니다.

오름차순을 저장하는 큐, 내림차순을 저장하는 큐를 모두 만들어주면 됩니다.

문제 조건

출력 예시

최솟값과 최댓값을 경우에 따라 제거해야 합니다.

이때 큐를 하나만 만들어서 구현을 하면 연산의 갯수가 너무 많기에 시간 초과가 생깁니다.

따라서 오름차순, 내림차순을 저장하는 큐를 만들어 각각 관리해줘야 합니다.

 

(221 , 221 , 15 , 13 , 100 , -50)의 수열이 주어졌다고 가정하겠습니다.

이때 최댓값은 221임으로 221을 삭제한다고 했을 때, 221 2개를 모두 없애는 것이 아닌 한개만 삭제해야합니다.

작은 수도 마찬가지로 2개 이상이 있을 경우에도 한개만 없애야합니다.

 

그렇기에 입력된 수가 같다고 해서 한번에 관리를 하면, 한개씩 삭제하는 것에 어려움이 생길 수 있어, queue에 저장을 할 때 pair를 사용해 (입력된 수, 순서)로 저장한 뒤 순서를 통해 관리했습니다.

 

문제를 봤을때 2개의 연산을 할 수 있습니다. 각 연산을 살펴보겠습니다.

1. I 연산

		if (order == 'I') {
			q_high.push(make_pair(num, i));
			q_low.push(make_pair(num, i));
			check[i] = 1;
		}

I 연산은 입력만 하면 됨으로 (입력된 수, 순서)로 2개의 queue에 모두 저장을 해줬습니다,

check 배열은 i번째 입력을 관리하는 배열입니다. (check[1] = 1 -> 첫번째 입력된 수가 존재한다.)

 

2. D 연산

		if (num == -1) {
			while (!q_low.empty()) {
				int X = q_low.top().second;
				if (check[X] == 1) break;
				q_low.pop();
			}
			if (q_low.size() > 0) {
				int X = q_low.top().second;
				check[X] = 0;
			}
		}
		else{
			while (!q_high.empty()) {
				int X = q_high.top().second;
				if (check[X] == 1) break;
				q_high.pop();
			}
			if (q_high.size() > 0) {
				int X = q_high.top().second;
				check[X] = 0;
			}
		}

D연산의 경우 2가지로 나뉩니다. -1 or 1 이 입력되었을때 각각 최솟값, 최댓값을 삭제해주면 됩니다.

두 연산은 거의 같음으로 -1일 경우로 설명하겠습니다.

 

먼저, 오름차순 queue에서 check값이 0인 값을 모두 빼줍니다.

check 값이 0이라는 의미는 이미 삭제된 수라는 의미이기 때문입니다. 

값을 빼준뒤, queue에 수가 남아있다면, 해당 수를 빼준뒤, 빼준 수의 순서의 check 값을 0으로 바꿔줍니다.

 

 

 

모든 연산이 끝났다면 2개의 큐에 수가 남아있는지의 여부를 통해 정답을 출력해주면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int test_case, N;
int check[1000001];

void solve() {
	cin >> N;
	priority_queue<pair<int,int>> q_high; // 내림차순
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q_low; // 오름차순
	for (int i = 0; i < N; i++) {
		char order;
		int num;
		cin >> order >> num;
		if (order == 'I') {
			q_high.push(make_pair(num, i));
			q_low.push(make_pair(num, i));
			check[i] = 1;
		}
		else if (order == 'D') {
			if (num == -1) {
				while (!q_low.empty()) {
					int X = q_low.top().second;
					if (check[X] == 1) break;
					q_low.pop();
				}
				if (q_low.size() > 0) {
					int X = q_low.top().second;
					check[X] = 0;
				}
			}
			else{
				while (!q_high.empty()) {
					int X = q_high.top().second;
					if (check[X] == 1) break;
					q_high.pop();
				}
				if (q_high.size() > 0) {
					int X = q_high.top().second;
					check[X] = 0;
				}
			}
		}
	}
	while (!q_low.empty()) {
		int X = q_low.top().second;
		if (check[X] == 1) break;
		q_low.pop();
	}
	while (!q_high.empty()) {
		int X = q_high.top().second;
		if (check[X] == 1) break;
		q_high.pop();
	}
	if (q_high.empty() && q_low.empty()) cout << "EMPTY" << "\n";
	else cout << q_high.top().first << " " << q_low.top().first << "\n";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		solve();
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요