[G5] 백준 22252번 정보 상인 호석 C++ 우선순위 큐, 해시맵

리뷰

 

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

해시맵과 우선순위 큐 자료구조를 혼용하여 풀이하는 문제

 

 

전역 변수

• q : 쿼리의 개수를 저장할 변수
• dic : 각 고릴라가 보유한 정보의 가치를 내림차순으로 저장할 해시맵
• ans : 총 얻게 된 정보 가치의 총합을 저장할 변수
• i : 연산 정보를 저장할 변수
• k : 추가할 정보의 개수를 저장할 변수
• c : 정보의 가치를 저장할 변수
• b : 구매할 정보의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. q값을 입력 받고, q번의 쿼리를 수행한다.
2. 매 쿼리마다 i, name에 값을 입력받고, 정수형 우선순위 큐 v에 dic[name]의 주소를 참조한다.
3. i가 1일 경우 k에 값을 입력 받고, k번의 while루프를 수행한다. 매 루프마다 c값을 입력 받아 v에 c를 추가한다.
4. i가 2일 경우 b에 값을 입력 받고, v가 비거나 b가 0이 될때까지 후위 순회하며 while루프를 수행한다.
5. 매 루프마다 ans에 v의 top()요소를 더해주고, pop()처리해준다.
6. 모든 쿼리를 수행한 후에 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. ans가 int범위를 넘어설 수 있기 때문에 long long타입으로 지정해주었다.

 

정답 코드

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

int q;
unordered_map<string, priority_queue<int>> dic;
long long ans;
int i, k, c, b;
string name;

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

	cin >> q;
	while (q--) {
		cin >> i >> name;
		priority_queue<int>& v = dic[name];

		if (i == 1) {
			cin >> k;

			while (k--) {
				cin >> c;
				v.push(c);
			}
		}
		else {
			cin >> b;

			while (!v.empty() && b--) {
				ans += v.top();
				v.pop();
			}
		}
	}
	cout << ans;
}