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

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

21939번: 문제 추천 시스템 Version 1

---

문제 추천 시스템은 이진 검색 트리를 이용하여 해결할 수 있습니다.

 

이진 검색 트리를 이용하면, 최대/최소값 구하기, 삽입, 삭제을 모두 O(logN)에 수행할 수 있습니다.

 

또한, 이진 검색 트리에 {l, p}를 삽입하면, 먼저, 난이도를 기준으로 정렬하고, 난이도가 같을 땐 문제 번호로 정렬하므로,

마지막 원소가 난이도가 가장 높으면서, 번호가 가장 큰 번호입니다.

첫번째 원소가 난이도가 가장 낮으면서, 번호가 가장 작은 원소입니다.

 

추가로, solved 명령을 수행할 때, {문제 번호, 난이도} 쌍을 찾기 위해서 map을 사용해주었습니다. 

 

아래는 전체 코드입니다.

 

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

set<pair<int, int>> db;
map<int, int> dict;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n;
    for(int i = 0; i < n; i++){
        int p, l; cin >> p >> l;
        db.insert({l, p});
        dict[p] = l;
    }
    
    cin >> m;
    for(int i = 0; i < m; i++){
        string op; cin >> op;

        if(op == "add"){
            int p, l; cin >> p >> l;
            db.insert({l, p});
            dict[p] = l;
        }else if(op == "recommend"){
            int x; cin >> x;
            if(x == -1){    // 가장 쉬운 문제의 번호를 출력
                cout << (*db.begin()).second << "\n";
            }else{  // x == 1, 가장 어려운 문제의 번호를 출력
                cout << (*prev(db.end())).second << "\n";
            }
        }else{  // op == "solved"
            int p; cin >> p;
            db.erase({dict[p], p});
            dict.erase(p);
        }
    }
}