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

풀이요약

treeset

풀이상세

1. 문제에서 원하는 출력은, 1 인 경우 가장 높은 난이도 가운데 가장 큰 문제 번호를 -1 인 경우에는 가장 낮은 난이도 가운데 가장 작은 번호를 출력하는 것이다.

2. 이는 즉 오름차순 정렬인 경우, -1 이면 맨 앞의 값을 1 이면 맨 뒤의 값을 출력하면 된다.

3. 단, solved 의 경우 set의 특정값을 지우기 위해서는 난이도를 직접 찾아야 하는데 이를 위해 배열을 하나 만들어 문제에 대한 난이도 값을 저장하기로 하자.

배운점

• cpp 의 map과 set은 기본적으로 treeset, treemap을 기반으로 한다.
• set 의 경우 기본 정렬은 오름차순이며, pair 를 사용하는 경우에는 첫번째 값을 먼저 비교한 후 동일하면 두번째 값을 비교하여 정렬한다.

#include <iostream>
#include <set>
using namespace std;
typedef pair<int, int> pii;
set<pii> s;
int arr[100000 + 1];

void input() {
    int N, P, L;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> P >> L;
        s.insert({L, P});
        arr[P] = L;
    }
}

void output(int X) {
    if (X == -1) cout << (*s.begin()).second << "\n";
    else cout << (*prev(s.end())).second << "\n";
}

void solve() {
    int M, P, L;
    cin >> M;
    string str;
    for (int i = 0; i < M; i++) {
        cin >> str;
        if (str == "add") {
            cin >> P >> L;
            s.insert({L, P});
            arr[P] = L;
        } else if (str == "solved") {
            cin >> P;
            s.erase({arr[P], P});
				    arr[P] = 0;
        } else {
            cin >> P;
            output(P);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
    input();
    solve();
}