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

/*
BOJ 21939 문제 추천 시스템 Version 1 의 코드입니다.
효율적이지 않은 풀이이니,, 다른 분의 풀이를 참고하시는 것을 추천합니다..!
*/

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

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

 

 

정답 코드

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

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

    multiset<pair<int, int>> hard; // 난이도 | 문제번호
    map<int, int> Map;             // 문제 번호 | 난이도

    int N, M, P, L;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> P >> L; // 문제 번호 | 난이도

        hard.insert(make_pair(L, P));
        Map[P] = L;
    }

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        string cmd;
        int arg1, arg2;
        cin >> cmd;
        if (cmd == "recommend")
        {
            cin >> arg1; // 1 or -1

            if (arg1 == 1)
            {
                // 가장 어렵고 문제 번호가 가장 큰거
                auto it = prev(hard.end());

                cout << it->second << "\n";
            }
            else
            {
                auto it = hard.begin();

                cout << it->second << "\n";
            }
        }
        else if (cmd == "add")
        {
            cin >> arg1 >> arg2; // 문제 번호 | 난이도

            hard.insert(make_pair(arg2, arg1));
            Map[arg1] = arg2;
        }
        else
        {
            cin >> arg1;

            int lev = Map[arg1];

            auto it = hard.find(make_pair(lev, arg1));

            hard.erase(it);
        }
    }
}

 

recommend와 add 까지는 multiset 만으로도 충분했습니다. 

하지만 solved 명령은 문제 번호가 주어지면, 그 문제 번호를 second 값으로 갖고있는 pair를 set 안에서 찾아야 했습니다. 이는 난이도 1부터 100까지 반복문을 돌려서 find 할 수 있지만, 편의를 위해 map을 이용하여 key로 문제 번호(P), value로 문제의 난이도(L)을 저장했습니다. 

 

 

pair multiset의 경우 first 값이 같다면, second 값을 기준으로 오름차순으로 정렬하기 때문에 recommend 명령어를 실행할 때

가장 쉬운 난이도 중에서 가장 작은 문제 번호를 가진 문제는 multiset의 begin에 위치하고 있었고,
가장 어려운 난이도 중에서 가장 큰 문제 번호를 가진 문제는 multiset의 end에 위치하고 있어서 해결이 쉬웠습니다.