[G2] 백준 21944번 문제 추천 시스템 Version2 C++ 해시, 집합, 맵, set, map

리뷰

 

간만에 풀어본 해시맵 문제, 파이썬으로 숙달한 사람은 map에 익숙해 지는 것 같다.

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

 

전역 변수

• n, m : 초기에 입력되는 문제의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 m
• Prob : 문제의 난이도와 알고리즘 분류 정보를 저장할 구조체
• probs : 문제 정보를 저장할 Prob 타입 배열, 문제 번호를 index로 사용하여 관리, 크기는 최대문제 번호 10만 + 1
• rec1 : recommed입력 시 문제 정보를 출력할 맵, 알고리즘 분류를 키로 가지며 int와 set<pair> 쌍으로 관리해 준다.
• rec2 : 알고리즘 분류 상관 없이 문제의 난이도로만 출력을 관리할 set, pair을 통해 난이도와 문제 번호를 관리한다.

 

함수

main외에 별도의 함수로 관리하진 않았다.

변수 및 자료 구조가 모두 전역 변수로 설정되어 있어 각각의 order를 함수로 관리해도 무방하다.

 

 

문제풀이

1. n을 입력 받고 초기 문제 정보를 받아와 rec1, rec2, probs에 문제 정보를 추가해 준다.
2. 이때 rec1는 알고리즘 분류를 키로 가지며, 난이도, 번호를 오름차순으로 관리해 준다.
3. rec2는 난이도, 번호를 오름차순으로 관리해 준다.
4. probs는 문제 번호를 인덱스로 가지며 해당 문제의 난이도, 번호 정보를 가진다.
5. m값을 입력 받고 m개의 쿼리문을 반복문을 통해 입력 받고 실행해 준다.
6. order을 입력 받고 각각 add, solved, recommend, recommend2, recommend3일때의 로직을 실행한다.
7. add : 초기 문제 정보를 받을때와 로직이 동일하다.
8. solved : 문제 번호를 입력 받고 probs에서 해당 문제의 정보를 가져와 rec1, rec2에서 문제를 제거해 준다.
9. recommend : x가 1일경우 g를 키로하는 rec1 세트의 맨 마지막 인자를 출력, 반대는 첫번째 인자를 출력해준다.
10. recommend2 : x가 1일경우 rec2의 맨 마지막 인자를 출력, 반대는 첫번째 인자를 출력해준다.
11. recommend3 : x가 1인 경우 lower_bound를 통해 rec2에서 문제 난이도가 L이상, 문제 번호는 0 이상을 찾아 그러한 문제가 존재한다면 해당 이터레이터의 값을 출력해 주면 된다, x가 -1인 경우 똑같이 해당 이터레이터를 반환 받고 rec2의 첫번째 인자가 아니라면 현재 이터레이터의 이전 이터레이터 값을 출력해 주면 된다.

 

참고 사항

1. set 자료구조는 pair를 첫번째 인자로 오름차순 정렬, 만약 첫번째 인자가 같다면 두번째 인자로 오름차순 정렬해 준다.
2. lower_bound를 통해 찾은 값을 이터레이터가 begin이 아닐때 --it을 해주면 찾고자 하는 값보다 작은 최대값을 찾을 수 있다.

 

정답 코드

#include<iostream>
#include<set>
#include<unordered_map>
#include<algorithm>

using namespace std;

int n, m;

struct Prob {
	int l, g;
};
Prob probs[100001];

unordered_map<int, set<pair<int, int>>> rec1;
set<pair<int, int>> rec2;

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

	cin >> n;
	while (n--) {
		int p, l, g; cin >> p >> l >> g;
		rec1[g].insert({ l, p });
		rec2.insert({ l, p });
		probs[p] = { l, g };
	}
	cin >> m;
	while (m--) {
		string order; cin >> order;
		if (order == "add") {
			int p, l, g; cin >> p >> l >> g;
			probs[p] = { l, g };
			rec1[g].insert({ l, p });
			rec2.insert({ l, p });
		}
		else if (order == "solved") {
			int p; cin >> p;
			Prob& prob = probs[p];
			int l = prob.l, g = prob.g;
			rec1[g].erase({ l, p });
			rec2.erase({ l, p });
		}
		else if (order == "recommend") {
			int g, x; cin >> g >> x;
			if (x == 1) {
				auto it = rec1[g].rbegin();
				cout << (*it).second << "\n";
			}
			else {
				auto it = rec1[g].begin();
				cout << (*it).second << "\n";
			}
		}
		else if (order == "recommend2") {
			int x; cin >> x;
			if (x == 1) {
				auto it = rec2.rbegin();
				cout << (*it).second << "\n";
			}
			else {
				auto it = rec2.begin();
				cout << (*it).second << "\n";
			}
		}
		else {
			int x, L; cin >> x >> L;
			if (x == 1) {
				auto it = rec2.lower_bound({ L, 0 });
				if (it == rec2.end()) cout << -1 << "\n";
				else cout << (*it).second << "\n";
			}
			else {
				auto it = rec2.lower_bound({ L, 0 });
				if (it == rec2.begin()) cout << -1 << "\n";
				else cout << (*--it).second << "\n";
			}
		}
	}
}