[BOJ/C++] 문제 추천 시스템 Version 1(21939번)

1. 개요

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

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

1-1. 설명

코딩 테스트 대비 문제를 직접 뽑아 "문제 번호, 난이도"로 정리했다. 이때 새로운 기능을 추가해보고자 한다. 

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을때만 주어지며, solved는 추천 문제 리스트에 번호가 하나 이상 있을때 주어진다. 이를 토대로 추천 시스템을 만들어보자. 

1-2. 제한 사항

 - 첫 줄에 추천 문제 리스트에 있는 문제 개수 N이 주어짐, N은 1 이상 100,000 이하 자연수

 - 다음줄부터 N+1줄까지 문제 번호 P와 난이도 L이 주어지며, P는 1 이상 100,000 이하 자연수, L은 1 이상 100 이하 자연수

 - N+2줄은 입력될 명령문 개수 M이 주어지며, M은 1 이상 10,000 이하 자연수

 - 그 다음 줄부터 M개 위에 설명한 명령문이 입력됨

 - recommend 명령이 주어질 때마다 문제 번호 한줄씩 출력

---

2.구현

2-1. 풀이

트리를 이용하여 풀고자 set 컨테이너를 사용하였다. 하지만 검색 부분에서 자꾸 시간초과가 발생하여 고민을 하던 중, 문제의 번호와 난이도를 저장해 바로 지울 수 있게끔 하면 된다는 풀이를 참고하여 map을 통해 문제의 번호와 난이도를 저장해주고 검색할 때 사용하게끔 하였다. 

2-2. 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <set>

using namespace std;

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

    int N, M, P, L;
    cin >> N;
    set<pair<int, int>> problems; // 추천 문제 리스트
    map<int, int> difficulty; // 빠른 검색을 위한 문제 난이도 저장하는 컨테이너

    while (N--) {
        cin >> P >> L;
        problems.insert({ L, P });
        difficulty[P] = L;
    }

    cin >> M;
    string inputStr;
    while (M--) {
        cin >> inputStr;
        if (inputStr == "add") { // 추가
            cin >> P >> L;
            problems.insert({ L, P });
            difficulty[P] = L;
        }
        else if (inputStr == "recommend") { 
            cin >> L;
            if (L == 1) { // 어려운 문제 추천
                auto iter = problems.end();
                iter = --iter;
                cout << iter->second << "\n";
            }
            else { // 쉬운 문제 추천
                auto iter = problems.begin();
                cout << iter->second << "\n";
            }
        }
        else if (inputStr == "solved") {
            cin >> P;
            problems.erase({ difficulty[P], P }); // 삭제
        }
    }

    return 0;
}