문제 풀이

map과 우선순위 큐를 사용하면 간단히 풀리는 문제, 작은 실수로 계속 풀리지 않아 고생했었다.

type 1을 입력받으면 map을 사용해서 map에 등록된 상인이 아니라면 idx를 부여해준다.
그리고 그 이름에 부여된 idx를 통해서 우선순위큐에 정보의 값들을 넣어준다.

type 2를 입력받으면 우선순위큐의 top에는 가장 값비싼 정보들이 들어 있으므로 원하는 만큼 pop해주면 된다.

문제 링크

boj/22252

소스코드

PS/22252.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
#include<queue>
using namespace std;

priority_queue<long long> pq[100005];
map<string, int> m;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long idx = 1;

	long long ans = 0;
	long long q;
	cin >> q;
	while (q--)
	{
		string name;
		int type;
		cin >> type;
		if (type == 1)
		{
			int n;
			cin >> name;
			if (!m[name])
				m[name] = idx++;
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				long long val;
				cin >> val;
				pq[m[name]].push(val);
			}
		}
		else if (type == 2)
		{
			cin >> name;

			long long n;
			cin >> n;
			if (!m[name])
				continue;
			long long _idx = m[name];
			long long max = min(n, (long long)pq[_idx].size());
			while (max--)
			{
				ans += pq[_idx].top();
				pq[_idx].pop();
			}
		}
	}
	cout << ans;

}