이진 검색 트리(2) - 문제 추천 시스템, 홍익 투어리스트

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

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

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/solutions/21939.cpp

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

unordered_map<int,int> PtoL; //문제별 난이도 저장
set<int> LtoP[102]; //난이도별로 문제 저장 
int n;

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    while(n--){
        int P,L; cin>>P>>L;
        PtoL[P]=L;
        LtoP[L].insert(P);
    }
    cin>>n;
    while(n--){
        string op; cin>>op;
        if(op=="add"){
            int P,L; cin>>P>>L;
            PtoL[P]=L;
            LtoP[L].insert(P);
        }
        if(op=="recommend"){
            int x; cin>>x;
            if(x==1){
                for(int i=100;i>=1;i--){
                    if(LtoP[i].empty()) continue;
                    cout<<*prev(LtoP[i].end())<<'\n';
                    break;
                }
            }
            if(x==-1){
                for(int i=1;i<=100;i++){
                    if(LtoP[i].empty()) continue;
                    cout<<*LtoP[i].begin()<<'\n';
                    break;
                }
            }
        }
        if(op=="solved"){
            int P; cin>>P;
            LtoP[PtoL[P]].erase(P);
        }
    }
    return 0;
}

---

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

23326번: 홍익 투어리스트

명소의 번호만 set에 담는다. 도현이의 이동은 수적 감각의 부족으로 1~N 으로 하지 못하고 0~N-1로 한 다음 연산에 사용할 때에만 +1을 해서 사용했다...

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

int N,Q;
int cur;
set<int> s;

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        int a; cin>>a;
        if(a) s.insert(i);
    }
    while(Q--){
        int query; cin>>query;
        
        //i번 토글
        if(query==1){
            int i; cin>>i;
            if(s.find(i)!=s.end()) s.erase(i);
            else s.insert(i);
        }

        //도현이가 시계방향으로 x 이동
        if(query==2){
            int x; cin>>x;
            cur=(cur+x)%N;
        }

        //명소에 도착하기 위해 시계방향으로 최소 몇 칸 이동해야 하는가
        //명소가 없으면 -1
        if(query==3){
            if(s.empty()) cout<<-1<<'\n';
            else{
                auto it = s.lower_bound(cur+1);
                if(it!=s.end()) cout<<*it-(cur+1)<<'\n';
                else cout<<N-(cur+1)+*s.begin()<<'\n';
            }
        }
    }
    return 0;
}

---

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

21944번: 문제 추천 시스템 Version 2

솔직히 어렵다기보다는 상당히 귀찮은 문제였다. 

#include <bits/stdc++.h>
using namespace std;
#define Level first
#define Algorithm second

//삭제를 위해 i번 문제의 난이도, i번 문제의 알고리즘을 저장해야 함
//난이도별로 문제를 저장하는 set 1개 
//알고리즘별로 문제를 저장하는 set 1개

int n;
pair<int,int> Pdata[100003]; //P번 인덱스애 {난이도, 알고리즘} 저장
set<int> Ls[103]; //난이도 L인 곳에 문제번호 P 저장 (문제번호순 정렬)
set<int> GLs[103][103]; //알고리즘 G, 난이도 L인 곳에 문제번호 P 저장 (문제번호순 정렬)

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    while(n--){
        //문제번호 난이도 알고리즘 순 입력
        int P,L,G; cin>>P>>L>>G;
        Pdata[P] = {L,G};
        Ls[L].insert(P);
        GLs[G][L].insert(P);
    }
    cin>>n;
    while(n--){
        string op; cin>>op;
        if(op=="solved"){
            int P; cin>>P;
            Ls[Pdata[P].Level].erase(P);
            GLs[Pdata[P].Algorithm][Pdata[P].Level].erase(P);
        }
        if(op=="add"){
            int P,L,G; cin>>P>>L>>G;
            Pdata[P]={L,G};
            Ls[L].insert(P);
            GLs[G][L].insert(P);
        }

        //알고리즘 분류가 G인 문제중 가장 어려운/쉬운 문제 출력
        if(op=="recommend"){
            int G,x; cin>>G>>x;
            if(x==1){
                for(int L=100;L>=1;L--){
                    if(GLs[G][L].empty()) continue;
                    cout<<*prev(GLs[G][L].end())<<'\n';
                    break;
                }
            }
            if(x==-1){
                for(int L=1;L<=100;L++){
                    if(GLs[G][L].empty()) continue;
                    cout<<*GLs[G][L].begin()<<'\n';
                    break;
                }
            }
        }
        
        //어렵고 문제 번호가 큰 것/ 쉽고 문제 번호가 작은 것
        if(op=="recommend2"){
            int x; cin>>x;
            if(x==1){
                for(int L=100;L>=1;L--){
                    if(Ls[L].empty()) continue;
                    cout<<*prev(Ls[L].end())<<'\n';
                    break;
                }
            }
            if(x==-1){
                for(int L=1;L<=100;L++){
                    if(Ls[L].empty()) continue;
                    cout<<*Ls[L].begin()<<'\n';
                    break;
                }
            }
        }

        //난이도 L보다 크거나 같은 문제 중 가장 쉬운 문제를 번호가 작은 순으로, 없다면 -1
        //난이도 L보다 작은 문제중 가장 어려운 문제를 번호가 큰 순으로, 없다면 -1
        if(op=="recommend3"){
            int x, L; cin>>x>>L;
            int ans=-1;
            //난이도 L보다 크거나 같은 문제 중 가장 쉬운 문제번호 출력
            if(x==1){
                for(int i=L;i<=100;i++){
                    if(Ls[i].empty()) continue;
                    ans=*Ls[i].begin();
                    break;
                }
            }
            if(x==-1){
                for(int i=L-1;i>=1;i--){
                    if(Ls[i].empty()) continue;
                    ans=*prev(Ls[i].end());
                    break;
                }
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}