[C++] 22252번: 정보 상인 호석

링크

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

22252번: 정보 상인 호석

문제

암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 사고파는 사람을 의미한다.

호석이는 아직 상인계의 새싹이기 때문에, 초기 투자를 통해서 여러 명의 "정보 고릴라"들로부터 정보를 모으려고 한다. 정보 고릴라란 여기저기서 정보를 수집하는 사람들을 의미한다. 일단 정보를 긁어모으기 위해서 호석이는 여러 정보 고릴라들에게 정보를 구매하려고 한다.

 

입출력 예제

예제 입력 1 복사

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

예제 출력 1 복사

44

코드

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

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	unordered_map<string, priority_queue<int>> info;
	int n;
	long long result = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int choice;
		int num;
		string name;

		cin >> choice >> name >> num;

		// 1 입력 받으면 정보상이 가진 정보 업데이트
		if (choice == 1)
		{
			for (int j = 0; j < num; j++)
			{
				int temp;
				cin >> temp;
				info[name].push(temp);
			}
		}

		// 2 입력 받으면 정보상이 가진 정보중 비싼 정보부터 구입
		else if (choice == 2)
		{
			if (info.find(name) == info.end())	continue; // 예외처리

			while (num-- && !info[name].empty())
			{
				result += info[name].top();
				info[name].pop();
			}
		}

	}

	cout << result << "\n";
	return 0;
}

풀이

• unordered_map과 우선순위 큐를 사용하여 풀었다.
• 처음엔 큐 대신 vector를 사용하여 sort로 내림차순 정렬하려 했지만 시간초과가 발생했다.
• queue와 priority_queue가 다른점은 큐는 FIFO형식으로 나오지만,
  우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 순으로 나온다.
  기본적으로 내림차순 정렬이며 greater로 오름차순, less로 내림차순을 나타낸다.
  (오름차순으로 사용 시 priority_queue<int, vector<int>,  greater<int>>와 같이 사용)
• 2번 입력 반복문에서 예외처리 조건을 while문 조건검사 안에 넣었다.
  for문을 사용하여 if로 예외처리 검사를 하니 시간초과가 나왔다.