백준 21939번: 문제 추천 시스템 Version1 (C++)

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

해당 문제의 핵심 접근 방법은 아래 두 가지와 같다.

• 해당 문제는 실제 번호에 해당하는 배열의 위치에 난이도를 넣어서 하나의 문제 번호만 존재하도록 관리한다.
• 위 배열을 참고해서 set 자료형을 배열로 선언하여 배열의 위치를 난이도로 하고 해당 배열에 문제 번호를 넣으면 문제 번호가 오름차순이 되기 때문에 문제에서 원하는 조건을 조금 더 쉽게 구현할 수 있다. 풀이는 아래와 같다.

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

int probl[100'002]; 
set <int> s[102];

int n,m;


int main()
{
    
    cin >> n;


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

    cin >> m;

    // for(auto& c: s)
    // {
    //     cout << c.first << ' ' << c.second << '\n';
    // }

    for(int i=0; i<m;i++)
    {
        string a;
       
        cin >> a;
        if(a=="recommend") 
        {
            int x;
            cin >> x;

            if(x==1)
            {
                for(int i=100; i>=1;i--)
                {
                    if(s[i].empty()) continue;
                    else
                    {
                        cout << *prev(s[i].end()) << '\n';
                        break;
                    }
                }
            }
            else if(x==-1)
            {
                  for(int i=1; i<=100;i++)
                {
                    if(s[i].empty()) continue;
                    else
                    {
                        cout << *(s[i].begin()) << '\n';
                        break;
                    }
                }

            }
        }
        else if(a=="add")
        {
            int p, l;
            cin >> p >> l;
            if(probl[p]==0)
            {
                probl[p]=l;
                s[l].insert(p);
            }
            else
            {
                s[probl[p]].erase(p);
                probl[p]=l;
                s[l].insert(p);
            }
        }
        else if(a=="solved")
        {
            int p;
            cin >> p; 

            s[probl[p]].erase(p);
        }


    }
}

아래는 바킹독님의 풀이다.

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/b08e041f30cd4b509604d115173e4fd9
#include 
using namespace std;

string op;
int N, L, P, x;
int probLevel[100'002];     // 이 문제가 어느 난이도였는지 저장
set probByLevel[102];  // 난이도별로 문제 저장
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  while (N--) {
    cin >> P >> L;
    probLevel[P] = L;
    probByLevel[L].insert(P);
  }
  cin >> N;
  while (N--) {
    cin >> op;
    if (op == "recommend") {
      cin >> x;
      if (x == 1) {
        for (int i = 100; 0 <= i; i--) {
          if (probByLevel[i].empty()) continue;
          cout << *(prev(probByLevel[i].end())) << '\n';
          break;
        }
      } else {
        for (int i = 0; i < 101; i++) {
          if (probByLevel[i].empty()) continue;
          cout << *probByLevel[i].begin() << '\n';
          break;
        }
      }
    } else if (op == "add") {
      cin >> P >> L;
      probLevel[P] = L;
      probByLevel[L].insert(P);
    } else if (op == "solved") {
      cin >> P;
      probByLevel[probLevel[P]].erase(P);
    }
  }
}