[BOJ / C++] 문제 추천 시스템 Version 1 (이진검색트리)

문제링크: https://www.acmicpc.net/problem/21939

 

1. 코드

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

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

    int n;
    cin >> n;
    
    set<pair<int, int>> S; // {난이도, 문제번호}
    vector<int> findLevel(100002, 0);

    while (n--) {
        int p, l;
        cin >> p >> l;

        S.insert(make_pair(l, p));
        findLevel[p] = l;
    }
    
    int m;
    cin >> m;
    while (m--) {
        string op;
        cin >> op;
        if (op == "add") {
            int p, l;
            cin >> p >> l;

            S.insert({l, p});
            findLevel[p] = l;
        }
        else if (op == "recommend") {
            int x;
            cin >> x;
            if (x == 1) {
                auto it = prev(S.end());
                cout << it->second << '\n';
            }
            else if (x == -1) {
                auto it = S.begin();
                cout << it->second << '\n';
            }
        } 
        else if (op == "solved") {
            int p;
            cin >> p;
            int l = findLevel[p];
            S.erase({l, p});
        }
    }
}

 

 

2. 시간복잡도

N = 100,000이고 M = 10,000이므로 O(NM)이 되면 시간초과 판정이 난다. 따라서 recommend, add, solved 모두 lgn에 처리가 가능해야한다. 이진검색트리인 set을 활용하면 insert, erase가 O(lgn)에 가능하다. 

mlgn = 10^4 * 20 < 10^8 이므로 시간제한 1초 내에 통과 가능하다. 

 

 

3. 분석

set을 활용하되, set "recommend"에서 가장 난이도가 높은 또는 낮은 문제를 출력해야하므로 난이도 순으로 정렬해야한다. 따라서 set<pair<int, int>> 이고 {난이도, 문제번호} 순으로 한다. 가장 어려운 문제가 여러개라면 문제번호가 큰 것을 출력해야하는 것도 고려한 조치이다.

 

solve에서는 문제 번호로 set에서 해당 pair를 지워야하는데 난이도를 모르기 때문에 찾아내는 것이 불가능하다. 따라서 문제번호마다 난이도를 저장하고 있는 큰 배열을 하나 만들어 놓고 add 연산에서 난이도 배열에도 값을 넣어주고 있다가 solve에서 해당 배열을 통해 문제의 난이도를 조회해서 pair로 만들어서 삭제해버리면 된다.