백준(BOJ) 정보 상인 호석 22252번 문제

정보 상인 호석 문제는 solved.ac 사이트에서 골드 5 난이도인 문제입니다. 우선순위 큐와 map을 사용하여 풀었으며, 우선순위 큐와 map을 사용하기 위해서는 <queue>와 <map> 헤더 파일이 필요합니다. 

 

문제 풀이 방법

• Key로 String을, Value로 우선순위 큐를 저장할 수 있는 map 변수를 생성합니다.
• k가 1일 때와 k가 2일 때를 나누어서 처리해줍니다.
  • k가 1일 때, key를 name으로 하여 우선순위 큐에 입력받은 숫자들을 저장합니다. 
  • k가 2일 때는 입력받은 name을 key로 가지는 value(코드에서는 우선순위 큐)에 값이 있어야 하고, b개수만큼의 정보 총합을 구해주어야 합니다. 따라서 두 가지 조건을 모두 만족하도록 반복문을 구성하였으며 코드를 보면 더욱 자세하게 알 수 있습니다.
• 우선순위 큐에 값을 저장하기 때문에 pop을 했을 때 큰 값이 먼저 나오게 되며, 나오는 값을 sum에 더해주어 마지막에 출력합니다.

 

주의 사항

• k의 최대가 10만이고, C의 최대도 10만이기 때문에 모두 다 더했을 때 int 형의 범위가 넘어가게 됩니다. 따라서 sum 변수의 자료형을 long long int로 해주었습니다.
• 고릴라가 가진 정보 < 호석이가 원하는 정보의 부분을 처리해주지 않으면 SegFault가 나오게 됩니다.

 

소스코드

#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

int main(void) {
	map<string, priority_queue<int>> mp;
	int t;
	long long int sum = 0;
	cin >> t;
	while (t--) {
		int k, num;
		string s;
		cin >> k >> s >> num;
		if (k == 1) {
			for (int i = 0; i < num; i++) {
				int c;
				cin >> c;
				mp[s].push(c);
			}
		}
		else if (k == 2) {
			while (!mp[s].empty() && num) {
				sum += mp[s].top();
				mp[s].pop();
				num--;
			}
		}
		
	}

	cout << sum << '\n';

}

정답-확인-이미지

개발 환경 : Visual Studio 2019