[백준] 22252 정보 상인 호석 c++

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

22252번: 정보 상인 호석

풀이

1. 고릴라가 가지는 정보의 가치는 arr벡터 배열에 저장한다.

2. 고릴라의 이름과  해당 고릴라가 파는 정보가 벡터의 몇번째에 들어 있는지는 map을 이용해서 저장한다.

ex) 

arr[0]  : 2 , 5 , 10 , 40, 1                             map  -> {'cpp',0},  {'java' ,1}

arr[1]  : 4, 3, 6 

3.고릴라의 이름이 map에 저장되어 있는지 확인한다.

4.없으면 map에 이름과 벡터의 몇번째에 저장할것인지 넣어주고 인덱스를 찾는다.
 고릴라의 이름이 있으면 map에서  인덱스를 찾는다.

5.쿼리가 1번이면 벡터의 인덱스 번째에 원소들을 저장하고 오름차순으로 정렬한다.

 6. 쿼리가 2 번이면 벡터의 해당 인덱스에 있는 원소들을 k개 만큼 sum에 더하고 벡터에서 삭제한다.
   (오름차순으로 되어있기 때문에 뒤에서부터 더한다.) 

    개수가 k보다 작다면 있는 만큼만 더한다.

7.  sum출력

 

sort로 정렬하면 시간초과가 날까봐 걱정했는데 시간초과가 나지 않아서 다행이다.

다른 사람은 multiset을 활용하여 풀었던 점이 인상적이였다.

ex) pair<string,multiset<int>> a[100001];

다른 사람 unordered_map<string, priority_queue<int>> um;

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

using namespace std;


vector<int>arr[100001];
map<string, int> name;


int main()
{
	int n;
	cin >> n;
	int temp;
	string nn = "";
	int k = 0;
	long long sum = 0;
	int idx = 0, index = 0;
	int a;
	//7
//1 Cpp 5 10 4 2 8 4
//1 Java 2 8 2
//2 Cpp 2
//1 Cpp 2 10 3
//2 Cpp 3
//2 Java 1
//2 Python 10
	while (n--)
	{
		cin >> temp >> nn >> k;
		//이름 찾고
		if (name.find(nn) != name.end())//있으면 몇번째 인지 찾아줌
		{
			index = name[nn];
		}
		else  //없으면 이름 삽입
		{

			name.insert({ nn, idx });
			index = idx;
			idx++;
		}
		if (temp == 1)
		{


			//원소 삽입
			while (k--)
			{
				cin >> a;
				arr[index].push_back(a);
			}

			//정렬
			sort(arr[index].begin(), arr[index].end());
		}
		else
		{
			//상위 k개 찾고 sum에 더하기
			while (k--)
			{
				if (arr[index].size() > 0)
				{
					sum += arr[index].back();
					arr[index].pop_back();
				}
				else
					break;
			}
		}

	}
	cout << sum << endl;
}