[BOJ] 22252. 정보 상인 호석 (data_structures, hash_set, priority_queue, tree_set)

Gold V

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

22252번: 정보 상인 호석

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

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

암흑가의 연락망은 빼곡하기 때문에 누가 어떤 정보를 얻었는지에 대한 찌라시들이 수시로 퍼진다. 찌라시로 알 수 있는 것은, 어떤 이름을 가진 고릴라가 C1, C2, ..., Ck 만큼의 가치가 있는 정보 k 개를 얻었다는 점이다.

호석이는 이를 바탕으로 임의의 시점에 특정 고릴라에게 정보를 몇 개 살 것인지를 정할 수 있다. 이때 가치 순으로 가장 비싼 정보들을 구매한다. 예를 들어 고릴라가 가진 정보가 10개이고, 호석이가 사고 싶은 정보 개수가 4개라면, 고릴라는 10개 중에서 가치 순으로 가장 비싼 4개를 팔 것이다. 한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다.

당신은 암흑가의 주먹이며 양대 산맥이 될 가능성이 있는 호석이를 주시하고 있다. 관찰하면서 얻은 정보는 총 Q 개이다. 각 정보는 다음의 2가지 중 하나이다.

• 1 Name k C1, C2, ..., Ck : 이름이 [Name]인 고릴라가 k 개의 정보를 얻었으며, 각 가치는 C1 부터 Ck 이다.
• 2 Name b : 호석이가 이름이 [Name]인 고릴라에게 b 개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼 b 개를 구매하며, 고릴라가 가진 정보가 b 개 이하이면 가진 모든 정보를 구매한다.

견제를 위해서 호석이가 가진 정보들의 가치 총합, 즉 호석이가 정보들을 구매하는 데에 쓴 돈의 총합을 구하자.

 

input:

• 고릴라들이 정보를 얻는 사건과 호석이가 거래하는 정보가 시간순으로 주어진다. 첫 번째 줄에는 쿼리의 개수 Q 가 주어진다.
• 이어서 Q 개의 줄에 걸쳐서 각 줄에 쿼리가 주어진다. 쿼리는 1이나 2로 시작한다.
• 1로 시작하는 경우에는 정보를 얻은 정보 고릴라의 이름과 k 가 주어지며 이어서 k 개의 정보 가치 C1, ..., Ck 가 자연수로 주어진다. 모든 Ci 는 1 이상 100,000 이하이다.
• 2로 시작하는 경우에는 호석이가 거래하려는 정보 고릴라의 이름과 구매하려는 정보의 개수 b 가 주어진다.

output:

• 모든 쿼리가 종료되었을 때에 호석이가 얻게 되는 정보 가치의 총합을 출력하라.

 

---

Idea :

• 고릴라의 [name]에 따라 가지고 있는 정보의 개수와 가치가 다름
  각 고릴라가 가진 정보 리스트를 고릴라의 [name]으로 구분지을 수 있어야 함 
  1. [name] 과 정보리스트로 구성된 고릴라 구조체 사용 
  2. [name]을 key로 하고 정보리스트를 value로 하는 map 사용
• 호석이가 비싼 정보부터 구매하기 때문에 각 고릴라가 가진 정보 리스트는 정보의 가치 기준 내림차순으로 정렬되어 있어야 함
  1. vector 사용, 호석이에게 판매할 때마다 내림차순 정렬
  2. priority_queue를 이용해 내림차순 정렬 상태 유지

Code 1: using map

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

using namespace std;

#define name first
#define info_list second

// 고릴라가 k개의 정보를 얻음 (쿼리 1)
void get_info(vector<int> &info_cost, int k) {
	int cost;
	while (k--) {
		cin >> cost;
		info_cost.push_back(cost);
	}
}

// 고릴라가 호석이에게 가장 비싼 b개의 정보를 판매 (쿼리 2) 
// 호석이가 얻은 정보의 가치 합을 리턴
int sell_info(vector<int> &info_cost, int b) {
	int ret = 0;
	sort(info_cost.begin(), info_cost.end());
	while (b-- && !info_cost.empty()) {
		ret += info_cost.back(); info_cost.pop_back();
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int Q, query, cnt;
	string name;
	map<string, vector<int>> gorillas;  // 정보를 가진 고릴라 리스트 
	long long answer = 0;               // 호석이가 가진 정보의 가치 총합 

	cin >> Q;
	while (Q--) {
		cin >> query >> name >> cnt;
		auto it = gorillas.find(name);  // 고릴라 리스트에 [name]과 동일한 고릴라가 있는지 탐색 
		switch (query) {	
			case (1): // gorilla gets some info
				if (it == gorillas.end()) { // 고릴라 리스트에 [name] 고릴라가 없으면 리스트에 새로 추가 
					vector<int> tmp;
					it = (gorillas.insert(make_pair(name, tmp))).first;
				}
				get_info(it->info_list, cnt);
				break;
			case (2): // HS buys info
				if (it != gorillas.end())   // 고릴라 리스트에 [name] 고릴라가 있을 경우에만 정보 구매 
					answer += sell_info(it->info_list, cnt);
				break;
		}
	}
	cout << answer << "\n";
}

 

Code 2: using gorilla struct

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>  // find_if

using namespace std;

struct Gorilla {
	string name;            // 고릴라 이름
	vector<int> info_cost;  // 고릴라가 가지고 있는 정보의 가치

	Gorilla(string _n) : name(_n) {}
	
	// 고릴라가 k개의 정보를 얻음 (쿼리 1)
	void get_info(int k) {
		int cost;
		while (k--) {
			cin >> cost;
			info_cost.push_back(cost);
		}
	}

	// 고릴라가 호석이에게 가장 비싼 b개의 정보를 판매 (쿼리 2) 
	// 호석이가 얻은 정보의 가치 합을 리턴 
	int sell_info(int b) {
		int ret = 0;
		sort(info_cost.begin(), info_cost.end());
		while (b-- && !info_cost.empty()) {
			ret += info_cost.back(); info_cost.pop_back();
		}
		return ret;
	}
};

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int Q, query, cnt;
	string name;
	vector<Gorilla> gorillas;   // 정보를 가진 고릴라 리스트 
	long long answer = 0;       // 호석이가 가진 정보의 가치 총합 

	cin >> Q;
	while (Q--) {
		cin >> query >> name >> cnt;
		// 고릴라 리스트에 [name]과 동일한 고릴라가 있는지 탐색 
		auto it = find_if(gorillas.begin(), gorillas.end(), [name](Gorilla &a) {
			return a.name == name;
		});
		switch (query) {	
			case (1): // gorilla gets some info
				if (it == gorillas.end()) { // 고릴라 리스트에 [name] 고릴라가 없으면 리스트에 새로 추가 
					gorillas.push_back(Gorilla(name));
					it = gorillas.end() - 1;
				}
				it->get_info(cnt);
				break;
			case (2): // HS buys info
				if (it != gorillas.end())  // 고릴라 리스트에 [name] 고릴라가 있을 경우에만 정보 구매 
					answer += it->sell_info(cnt);
				break;
		}
	}
	cout << answer << "\n";
}

---

Result : 

Code 1) 메모리: 3748 KB, 시간: 148 ms

Code 2) 메모리: 3760 KB, 시간: 152 ms 

 

Review :

• priority_queue는 정렬된 상태를 유지해야 하기 때문에 새로운 정보가 추가할 때 시간 소요됨
  반면에 vector의 경우, 정보 추가 시에 시간 소요가 적으나 정보를 팔기 전 정렬을 따로 해줘야 함
  이 문제에서는 추가되는 정보 개수가 정보를 파는 횟수보다 훨씬 많으므로 vector를 사용하는 것이 효율적
• 고릴라 구조체를 만들 경우, first, second를 사용하는 map과 달리 name, info_cost를 사용하므로 가독성이 좋고,
  정보 얻기, 정보 팔기 즉 고릴라의 행동과 관련된 함수를 고릴라 구조체로 묶을 수 있는 점이 좋음
• map을 이용할 경우, find 함수가 map 컨테이너에 만들어져 있기 때문에 key인 name을 기준으로 탐색할 때 유리, 코드가 훨씬 간결해지고 시간 측면에서도 효율적이었음

 

• 구조체 배열에서 find 사용 시 find_if와 람다 함수를 이용할 수 있다
• map의 insert의 리턴 값은 <삽입한 map iterator, insert 성공 여부 bool> pair 이다