[알고리즘] 백준 21939: 문제 추천 시스템 Version 1 (C++)

처음에는 map으로 풀어볼까 했다.

 

add를 할 때 난이도를 기준으로 저장해야지, recommend가 가능하니

first를 난이도로, second를 이름으로 지정했다.

 

solved 할 때가 문제였다.

find를 할 때 first(key)를 통해서 찾는데, 난이도는 중복이 가능하다.... 그래서 찾아서 없애는데 난항을 겪었다...

 

흠... 그럼 set을 사용해서 찾아볼까 했다. 

set<pair<int,int>> 로 만들어서 사용하였다. set 역시 난이도 기준으로 오름차순이 되어야하므로

first를 난이도, second를 문제 번호로 지정했다.

 

그러니까 생긴 문제.. ;;

find를 할 때, pair< 문제 번호 , 난이도>가 필요한데, 우리는 난이도를 알 방도가 없다...

 

 

흠.... set,, map,, 둘 다 안되네;;;;

이건 몰랐지? set, map을 같이 쓰면된다

 

set에서 find를 할려면 문제 번호와 난이도를 알아야한다. 우리는 지금 문제번호를 안다. ( 입력으로 들어오니까)

그럼 문제 번호를 통해서 난이도를 얻을 수 있는 map을 하나 만들면 된다. 
map< 문제번호, 난이도> 로 저장하면, 문제에 따른 난이도를 얻을 수 있다.

그럼 문제번호, 난이도 모두 얻을 수 있으니

set에서 삭제하면된다!! 그럼 완성

 

내 코드:

#include <iostream>
#include <queue>
#include <map>
#include <cstring>
#include <set>
using namespace std;
 

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(NULL); 
     
    
    map<int, int> mp;
    set<pair<int, int>> st; 


    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        int name;
        int level;

        cin >> name;
        cin >> level; 
        
        mp[name] = level;
        st.insert({ level, name });
    }

    int n;
    cin >> n; 

    for (int i = 0; i < n; i++)
    {

        string ord;
        cin >> ord;

        if (strcmp(ord.c_str(), "add") == 0)
        {
            int name;
            int level;

            cin >> name;
            cin >> level; 
            mp[name] = level; 
            st.insert({ level, name });
        }
        else if (strcmp(ord.c_str(), "recommend") == 0)
        {
            int level;
            cin >> level;
            if(level == 1)
            { 
                cout << st.rbegin()->second  << "\n";
            }
            else if (level == -1)
            { 
                cout << st.begin()->second << "\n";
            }
        }
        else if (strcmp(ord.c_str(), "solved") == 0)
        {
            int id;
            cin >> id;
            
            int level = mp[id]; 
            auto it2 = st.find({ level, id  });
            
            mp.erase(id);
            st.erase(it2);
        }
    }
        return 0;
}

 

정석코드:

내 코드와 동일~!