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);
}
}
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 11718번: 그대로 출력하기 (C++) (0) | 2024.01.31 |
---|---|
백준 23326번: 홍익 투어리스트 (C++) (0) | 2024.01.31 |
백준 1202번: 보석 도둑(C++) (0) | 2024.01.31 |
백준 7662번: 이중 우선순위 큐 (C++) (0) | 2024.01.31 |
백준 9375번: 패션왕 신해빈 [C++] (0) | 2024.01.31 |