문제 출처

1. 문제설명

  • 자세한 설명은 문제 링크 참조
  • 문제 번호, 난이도가 주어진다.
  • 이후 명령어가 주어진다.
    • recommend x : 문제 중 난이도가 가장 높은/낮은 문제 번호 출력
      • x == 1, 난이도가 가장 높은 문제
      • x == -1, 난이도가 가장 낮은 문제
      • 여러 개인 경우 문제 번호가 가장 큰/작은 것으로 출력
    • add P L : 문제 번호 P, 난이도 L 추가
    • solved P : 문제 번호 P 제거



2. 알고리즘 설계

  • set을 이용해 풀이하였다.
  • 문제 번호는 중복될 수 없으므로, int 배열을 선언하였다.
    • 각 원소는 문제의 난이도를 저장한다.
    • arr[문제 번호] = 난이도
  • 난이도는 중복될 수 있으므로, set 배열을 선언하였다.
    • set[난이도].insert(문제 번호)
  • 구현이 그나마 까다로운 부분이 recommend라고 생각해 해설해보겠다.
    • recommend
      • set은 기본적으로 큰 수가 뒤에 정렬된다.
      • 만약 set[n].empty()가 true라면, 해당 난이도에 저장된 문제가 없다는 뜻이다.
      • false를 최초로 만나는 n이 정답인데…
        • 앞서 언급했듯 같은 난이도에 여러 문제가 있을 수 있다.
        • 쉬운 문제라면 번호가 작은 게 정답이므로 begin()
        • 어려운 문제라면 번호가 큰 게 정답이므로 prev(end())
          • iterator end()는 N+1 번째 위치이므로 prev를 해줘야 마지막 원소가 된다.



3. 전체 코드

  • 변수는 편의상 재사용 하였다!
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int n, p, l, m;
string opt;

int P[100005];
set<int> L[105];

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

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> p >> l;
        P[p] = l;
        L[l].insert(p);
    }

    cin >> m;
    while(m--) {
        cin >> opt;

        if(opt == "recommend") {
            cin >> p;

            if(p == 1) {
                for(int i=100; i>=0; i--)
                    if(!L[i].empty()) {
                        cout << *prev(L[i].end()) << '\n';
                        break;
                    }
            }
            else {
                for(int i=0; i<=100; i++)
                    if(!L[i].empty()) {
                        cout << *L[i].begin() << '\n';
                        break;
                    }
            }
        }
        else if(opt == "add") {
            cin >> p >> l;
            P[p] = l;
            L[l].insert(p);
        }
        else {
            cin >> p;
            L[P[p]].erase(p);
        }
    }

    return 0;
}