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

이 문제에서는 문제 리스트에서 문제의 추가/삭제가 빈번히 일어나고 빠르게 문제를 찾아줘야하기 때문에, 트리 형태의 자료구조를 사용하는 것이 좋다.

그렇다면, 난이도와 문제 번호를 어떻게 관리해야 효율적일까?

우리는 {난이도, 문제번호}를 set<pair<int, int>>을 통해 관리하면 문제 추천은 쉽게 구현이 가능하다.

하지만, 문제 $P$를 풀어서 삭제해야 한다면, 난감해진다. 모든 원소에 대해서 문제 번호가 $P$라면, 삭제를 진행하므로 한 번의 solved 명령에 O(NlogN)의 시간 복잡도가 소요된다.

따라서, 전체 시간복잡도는 O(NKlogN)이 되므로 시간 초과가 발생한다.

하지만, $L$이 100이하이므로 난이도별로 문제를 set으로 관리하면 O(LlogN)으로 문제를 solved를 처리해 줄 수 있다.

또, recomend의 경우도 O(LlogN)으로 해결이 가능하다.

그리고, add의 경우에는 난이도를 알고 있으므로 O(logN)이 된다.

따라서, 전체 시간 복잡도는 O(KLlogN)으로 시간 내에 통과된다.

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

int n, m;
set<int> problems[101];

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

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

	cin >> m;
	while (m--) {
		string cmd;
		cin >> cmd;

		if (cmd == "recommend") {
			int x;
			cin >> x;
			if (x < 0) {
				for (int i = 1; i <= 100; i++) {
					if (!problems[i].empty()) {
						cout << *problems[i].begin() << "\n";
						break;
					}
				}
			} else {
				for (int i = 100; i >= 1; i--) {
					if (!problems[i].empty()) {
						cout << *prev(problems[i].end()) << "\n";
						break;
					}
				}
			}
		} else if (cmd == "add") {
			int p, l;
			cin >> p >> l;
			problems[l].insert(p);
		} else {
			int p;
			cin >> p;
			for (int i = 1; i <= 100; i++) problems[i].erase(p);
		}
	}
}