[G4] 백준 21939번 문제 추천 시스템 Version 1 C++ 우선순위 큐, 해시맵

리뷰

 

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

최대 힙과 최소 힙, 그리고 해시맵 자료구조를 사용하여 AC를 받은 문제

 

해당 문제의 상위 호환인 Version2 문제도 있다.

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

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

 

 

전역 변수

• n : 초기에 주어지는 문제의 개수를 저장할 변수
• p : 문제 입력 시 문제 번호를 저장할 변수
• l : 문제 입력 시 문제 난이도를 저장할 변수
• m : 쿼리문의 개수를 저장할 변수
• ASC : 문제 번호, 난이도를 정의하기 위한 구조체 문제난이도를 기준, 같다면 번호를 기준으로 오름차순 한다.
• DESC : 문제 번호, 난이도를 정의하기 위한 구조체 문제난이도를 기준, 같다면 번호를 기준으로 내름차순 한다.
• dic : 문제 존재 여부를 체크하기 위한 해시맵
• pq_asc : 문제의 번호와 난이도를 오름차순 정렬하기 위한 ASC타입의 최소 힙
• pq_desc : 문제의 번호와 난이도를 내림차순 정렬하기 위한 DESC타입의 최대 힙

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 요소의 문제 번호와 난이도를 입력 받아 dic, pq_asc, pq_desc에 저장해 준다.
2. m값을 입력 받고, m개의 쿼리문을 수행한다. 첫 번째로 명령어를 문자열 변수 op에 받아준다.
3. 만약 op가 "add"라면, 문제 번호와 난이도를 입력 받아 dic, pq_asc, pq_desc에 저장해 준다.
4. "recommend"라면, 변수 x에 값을 하나 입력받아준다.
5. x가 1이라면 pq_desc를 순회하며 dic상에 존재하지 않거나, 난이도가 일치하지 않은 문제를 모두 빼내어 준다.
6. 그러한 문제가 없다면 pq_desc의 top의 idx값을 출력해 준 뒤 줄바꿈을 진행해 준다.
7. x가 -1이라면 pq_asc를 기준으로 위 로직을 동일하게 수행해 준다.
8. "solved"라면, 문제 번호를 입력 받고, 해당 번호의 값을 dic에서 erase처리해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 문제 설명을 보면 "추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다." 라는 조건이 있다.
• 따라서 dic을 key는 문제의 번호로, value는 문제의 난이도로 저장해 주어야 한다.
• 우선순위 큐를 순회할 때 dic에 해당 문제가 존재하지 않는다면 혹은 문제의 난이도가 다르다면 그 문제를 제거한다.

 

정답 코드

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;

int n, p, l, m;
struct ASC {
	int idx, dif;
	bool operator<(const ASC& other) const {
		if (dif == other.dif) return idx > other.idx;
		return dif > other.dif;
	}
};
struct DESC {
	int idx, dif;
	bool operator<(const DESC& other) const {
		if (dif == other.dif) return idx < other.idx;
		return dif < other.dif;
	}
};
unordered_map<int, int> dic;
priority_queue<ASC> pq_asc;
priority_queue<DESC> pq_desc;

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

	cin >> n;
	while (n--) {
		cin >> p >> l;
		dic[p] = l;
		pq_asc.push({ p, l });
		pq_desc.push({ p, l });
	}

	cin >> m;
	while (m--) {
		string op; cin >> op;
		if (op == "add") {
			cin >> p >> l;
			dic[p] = l;
			pq_asc.push({ p, l });
			pq_desc.push({ p, l });
		}
		else if (op == "recommend") {
			int x; cin >> x;
			if (x == 1) {
				while (!pq_desc.empty()) {
					DESC desc = pq_desc.top();
					if (!dic[desc.idx] || dic[desc.idx] != desc.dif) pq_desc.pop();
					else break;
				}
				cout << pq_desc.top().idx << "\n";
			}
			else {
				while (!pq_asc.empty()) {
					ASC asc = pq_asc.top();
					if (!dic[asc.idx] || dic[asc.idx] != asc.dif) pq_asc.pop();
					else break;
				}
				cout << pq_asc.top().idx << "\n";
			}
		}
		else {
			int x; cin >> x;
			dic.erase(x);
		}
	}
}