백준 21939. 문제 추천 시스템 Version 1 (이진검색트리)
https://www.acmicpc.net/problem/21939
21939번: 문제 추천 시스템 Version 1
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령
www.acmicpc.net
multimap을 사용해서 구현하려고 했다.
이렇게 풀면 문제 레벨을 오름차순으로, 문제레벨이 같은경우 문제 번호로 다시 오름차순 정렬해야 한다.
정렬할 때부터 일단 답이 없을 뿐만아니라, add를 구현할 때에는 문제 레벨, 문제 번호 다 고려해야 되기 때문에
upper_bound를 아무리 사용해도 답이 없다.
그래서 이 풀이법을 포기하고 정답을 봤다^^ 코드 출처는 언제나 그렇듯 바킹독 깃허브이다.
https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/solutions/21939.cpp
1. 특징
1) 이진검색트리 (set, mutiset, map)
2. 구현 포인트
난이도 별로 문제를 set으로 저장한다는 것이 핵심이다.
난이도가 1이상 100이하의 자연수이기 때문에(크지 않아서) 이 풀이를 떠올리기 어렵지 않은듯하다 -> 나는 못함
난이도가 같은 문제 번호들은 정렬되어 있어야 하기 때문에 set을 떠올리는 것은 어렵지 않다 -> 이래서 문제를 잘 분석하고 풀어야함
3. 코드
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
//recommed 1: 추천 문제 리스트에서 가장 어려운 문제의 번호 출력, 가장 어려운거 여러 개이면 문제 번호가 큰것을 출력
//recommed -1: 가장 쉬운 문제 번호 출력, 여러개이면 번호가 가장 작은것 출력
//add p l: 리스트에 난이도 l인 문제 번호 p 추가
//solved -: p제거
string op;
int N, L, P, x;
int probLevel[100002]; //이 문제가 어느 난이도였는지 저장 // 1 <= p <= 100000
set<int> probByLevel[102]; //난이도별 문제 저장 // 1 <= L <= 100
int main()
{
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; i >= 0; i--)
{
if(probByLevel[i].empty()) continue;
cout << *(prev(probByLevel[i].end())) << '\n';
break;
}
}
else
{
for(int i = 0; i <= 100; 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);
}
}
}
3-1) 내가 이 풀이법을 떠올렸다면 아래와 같이 문제가 어느 난이도였는지 저장하는 배열(probLevel[100002])은 생각을 못하고, 다음과 같이 작성했을 거같다.
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
//1:50
//recommed 1: 추천 문제 리스트에서 가장 어려운 문제의 번호 출력, 가장 어려운거 여러 개이면 문제 번호가 큰것을 출력
//recommed -1: 가장 쉬운 문제 번호 출력, 여러개이면 번호가 가장 작은것 출력
//add p l: 리스트에 난이도 l인 문제 번호 p 추가
//solved -: p제거
string op;
int N, L, P, x;
set<int> probByLevel[102]; //난이도별 문제 저장 // 1 <= L <= 100
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
while(N--)
{
cin >> P >> L;
probByLevel[L].insert(P);
}
cin >> N;
while(N--)
{
cin >> op;
if(op == "recommend")
{
cin >> x;
if(x==1)
{
for(int i = 100; i >= 1; i--)
{
if(probByLevel[i].empty()) continue;
cout << *(prev(probByLevel[i].end())) << '\n';
break;
}
}
else
{
for(int i = 1; i <= 100; i++)
{
if(probByLevel[i].empty()) continue;
cout << *(probByLevel[i].begin()) << '\n';
break;
}
}
}
else if(op == "add")
{
cin >> P >> L;
probByLevel[L].insert(P);
}
else if(op == "solved")
{
cin >> P;
for(int i = 1; i <= 100; i++)
{
if(probByLevel[i].find(P) != probByLevel[i].end())
probByLevel[i].erase(P);
}
}
}
}