Koala - 4기

[BOJ] 정보 상인 호석 22252번

알 수 없는 사용자 2021. 7. 24. 02:31

정보 상인 호석 문제 정리

이번 문제는 우선순위 큐와 map을 사용하여 문제를 풀었습니다. key로 Name을 value로 우선순위 큐를 담아서 map을 구성해주었습니다.

  • 가치 순으로 가장 비싼 정보 : 우선순위 큐를 떠올림
  • Name에 따라 정보 가치가 저장된다는 점에서 map을 떠올림

처음 제출했을 때에는 "큐에 남아 있는 정보 가치의 개수 < 호석이가 거래하려고 하는 정보 개수"를 고려해주지 못해 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';

}