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

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

 

1. 코드

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

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

    int n;
    cin >> n;

    vector<set<pair<int, int>>> Set1(102); // 그룹별 {난이도, 문제번호}
    set<pair<int, int>> Set2; // {난이도, 문제번호}
    vector<pair<int, int>> findLevelGroup(100002); //{난이도, 그룹}

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

        Set1[g].insert({l, p});
        Set2.insert({l, p});
        findLevelGroup[p] = {l, g};
    }

    int m;
    cin >> m;
    while (m--) {
        string op;
        cin >> op;
        
        if (op == "recommend") {
            int g, x;
            cin >> g >> x;
            
            if (x == 1) {
                cout << prev(Set1[g].end())->second << '\n';
            }
            else {
                cout << Set1[g].begin()->second << '\n';
            }
        }
        else if (op == "recommend2") {
            int x;
            cin >> x;

            if (x == 1) {
                cout << prev(Set2.end())->second << '\n';
            }
            else {
                cout << Set2.begin()->second << '\n';
            }
        }
        else if (op == "recommend3") {
            int x, l;
            cin >> x >> l;

            if (x == 1) {
                auto it = Set2.lower_bound({l, INT_MIN}); 
                if (it == Set2.end()) cout << -1 << '\n';
                else cout << it->second << '\n';
            }
            else {
                auto it = Set2.lower_bound({l, INT_MIN});  // level >= l
                if (it == Set2.begin()) {
                    cout << -1 << '\n';
                } else {
                    --it;  // level < l 중 가장 큰 {level, p}
                    cout << it->second << '\n';
                }
            }
        }
        else if (op == "add") {
            int p, l, g;
            cin >> p >> l >> g;

            int oldL, oldG;
            tie(oldL, oldG) = findLevelGroup[p];
            if (oldL != 0) {
                Set1[oldG].erase({oldL, p});
                Set2.erase({oldL, p});
            }

            Set1[g].insert({l, p});
            Set2.insert({l, p});
            findLevelGroup[p] = {l, g};
        }
        else if (op == "solved") {
            int p;
            cin >> p;

            int l, g;
            tie(l, g) = findLevelGroup[p];
            Set1[g].erase({l, p});
            Set2.erase({l, p});
        }

    }
}

 

 

2. 시간복잡도

n = 100,000이고, m = 10,000 이므로 O(MN)으로 들어가면 시간초과가 된다. 따라서 M마다 주어지는 각 명령어는 모두 O(lgn)에 처리가 되어야한다. find, add, erase가 모두 O(lgn)에 되어야하므로 이진검색트리인 set 자료구조를 사용한다.

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

 

 

3. 분석

recommend에서는 문제 분류별로 가장 어려운, 쉬운 문제를 찾아내야한다. 그래서

    vector<set<pair<int, int>>> Set1(102); // 그룹별 {난이도, 문제번호}

를 만들었고 set이므로 자동으로 난이도 오름차순, 문제번호 오름차순으로 정렬된다.

 

recommend2에서는 전체에서 난이도가 가장 높은 순, 동일하면 문제번호가 큰 순으로 출력해야한다. 그래서

    set<pair<int, int>> Set2; // {난이도, 문제번호}

를 만들었다.

 

recommend3에서는 알고리즘 분류에 상관없이 (1) 난이도 L 이상 중 문제번호가 가장 작은 것 또는 (2) 난이도 L 미만 중 문제번호가 가장 큰 것을 출력해야하므로 Set2에서 lower_bound로 이상인 것 중에 가장 작은 것을 찾아내서 처리할 수 있다.

 

solved에서는 문제번호 p만 가지고 erase를 처리해야한다. 따라서 p로 기존의 l, g를 O(1)에 찾아낼 수 있도록 배열을 만들어준다.

    vector<pair<int, int>> findLevelGroup(100002); // {난이도, 그룹}

이렇게 하면 문제 번호로 바로 난이도, 그룹을 조회할 수 있다. 인덱스를 문제 번호로 쓴다.

 

add에서는 리스트에 있는 문제 번호가 다른 난이도와 분류로 들어올 수 있으므로 해당 부분 처리를 주의해줘야한다.

        else if (op == "add") {

            int p, l, g;

            cin >> p >> l >> g;

            int oldL, oldG; // 이전에 있는지 확인해서 있으면 지워줌

            tie(oldL, oldG) = findLevelGroup[p];

            if (oldL != 0) {

                Set1[oldG].erase({oldL, p});

                Set2.erase({oldL, p});

            }

            Set1[g].insert({l, p});

            Set2.insert({l, p});

            findLevelGroup[p] = {l, g};

        }