[백준 21944] 문제 추천 시스템 Version 2 (C++)

이 문제는 이전에 풀었던 문제 추천 시스템 Version 1의 시리즈 문제이다.

이 문제도 삽입과 삭제, 접근이 빈번히 이루어지고 원소들이 내부적으로 정렬된 상태를 유지하면 편할 것 같다.

따라서, 트리 형태의 자료구조에 데이터를 저장하는 게 좋아보인다.

recommend는 그룹 G와 x를 넘겨주는데, 분류가 G이면서 난이도가 최대 혹은 최소인 문제를 빠르게 찾아야 하므로 이를 위해서 set<pair<int, int>> group[101]로 {난이도, 번호}를 관리하면, x가 1이면 해당 분류의 맨 마지막 원소를 출력하면 되고, x가 -1이면 해당 분류의 첫번째 원소를 출력하면 된다.

recommend2는 x만을 넘겨주는데, x가 1인 경우 난이도가 어려운 것들 중 문제 번호가 큰 것, x가 -1인 경우 난이도가 쉬운 것들 중 문제 번호가 작은 것을 출력해야 한다.

이를 위해서, set<int> level[101]로 문제 번호를 난이도별로 관리하면 된다.

recommend3은 x과 난이도 L이 넘겨주는데, x가 1이면 난이도 L이상의 가장 쉬운 난이도의 문제들 중 문제 번호가 작은 것, x가 -1이면 난이도 L미만의 가장 어려운 난이도의 문제들 중 문제 번호가 큰 것을 출력해야 한다.

이는 L이 100이하로 충분히 작기 때문에, 난이도별로 문제를 관리하는 set<int> level[101]를 루프를 돌면서 처리하면 되는 문제이다.

하지만, 문제가 아예 없으면 -1을 출력해야하므로 flag변수를 이용해 해결해주어야한다.

add는 P, L, G를 넘겨주는데, 해당 값들을 통해 set<pair<int, int>> group[101]과 set<int> level[101]에 적절히 원소를 삽입하면 된다.

추가로, 삭제시에 O(1)로 처리하고 싶어서 문제 번호를 통해 난이도와 분류를 곧바로 알아낼 수 있도록 map<int, pair<int, int>> problem을 도입했다. problem[i]에는 {난이도, 분류}가 저장된다.
(map은 RBT로 구현되어서 O(logN)에 접근되는 것이 맞다. 정말 O(1)로 접근하고 싶으면 unordered_map을 사용하면 된다. 하지만, 해시 충돌이 잘 일어나지 않음이 전제되지 않았으므로, 그냥 map을 사용 하는게 좋다.)

solved는 문제 번호 P를 넘겨주는데, problem[P]로 해당 문제의 {난이도, 분류}에 곧바로 찾아낼 수 있고, 각각의 level[L]과 group[G]에서 문제에 해당하는 원소를 삭제해 주면 된다.

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

int n, m;
set<pair<int, int>> group[101]; // {레벨, 번호}
set<int> level[101];
map<int, pair<int, int>> problem; // 문제 번호 -> {레벨, 그룹}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int p, l, g;
		cin >> p >> l >> g;
		group[g].insert({l, p});
		level[l].insert(p);
		problem[p] = {l, g};
	}

	cin >> m;
	while (m--) {
		string c;
		cin >> c;
		if (c == "recommend") {
			int g, x;
			cin >> g >> x;
			if (x > 0) cout << prev(group[g].end())->second << "\n";
			else cout << group[g].begin()->second << "\n";
		} else if (c == "recommend2") {
			int x;
			cin >> x;
			if (x > 0) {
				for (int i = 100; i > 0; i--) {
					if (level[i].empty()) continue;
					cout << *prev(level[i].end()) << "\n";
					break;
				}
			} else {
				for (int i = 1; i <= 100; i++) {
					if (level[i].empty()) continue;
					cout << *level[i].begin() << "\n";
					break;
				}
			}
		} else if (c == "recommend3") {
			int x, l;
			bool isExist = 0;
			cin >> x >> l;
			if (x > 0) {
				for (int i = l; i <= 100; i++) {
					if (level[i].empty()) continue;
					cout << *level[i].begin() << "\n";
					isExist = 1;
					break;
				}
			} else {
				for (int i = l - 1; i > 0; i--) {
					if (level[i].empty()) continue;
					cout << *prev(level[i].end()) << "\n";
					isExist = 1;
					break;
				}
			}
			if (!isExist) cout << -1 << "\n";
		} else if (c == "add") {
			int p, l, g;
			cin >> p >> l >> g;
			group[g].insert({l, p});
			level[l].insert(p);
			problem[p] = {l, g};
		} else {
			int p, l, g;
			cin >> p;
			tie(l, g) = problem[p];
			level[l].erase(p);
			group[g].erase({l, p});
		}
	}
}