백준 22252 정보 상인 호석 풀이

 

힌트 1

시간 복잡도를 잘 생각하셔야 합니다!
만약 이미 90만 개의 원소가 배열에 있을 때, 나머지 쿼리 1만개에서 원소를 하나씩 넣고, 넣을 때마다 정렬한다고 합시다.
그렇게 되면 시간 복잡도는 대략 (10,000) * (100만 log 100만) 이 되어버립니다.

 

힌트 2

우선순위 큐(최대힙)의 원소 삽입에 걸리는 시간 복잡도는 logn입니다.

 

힌트 3

우리는 이 문제를 맵을 이용해 간단화 시킬 수 있습니다.

어떤 고릴라의 정보 배열을 나타낼 때 c++에서는 map<string, priority_queue<int>> 로 만든다면, 각 고릴라가 key값이 되고 해당 고릴라가 가진 정보들이 value가 됩니다. 

 

 

문제 풀이

얼핏 보면 정렬 문제 같지만, 절대 정렬로 풀면 안되는 문제입니다. 이유는 힌트 1에 있습니다!

 

문제에서 고릴라는 삽입 또는 삭제 연산만하며, 삭제 시 항상 가장 큰 수들만 삭제합니다.

이렇게 무지성으로 가장 큰 수들만 삭제하는 문제라면, 따로 정렬할 필요가 없는 우선 순위 큐를 사용하는 것이 좋습니다.

하지만 이것 또한 만약 문제 제한에서 모든 쿼리에 대한 k 의 합은 1,000,000 을 넘지 않는다. 라는 조건이 없었다면, 최악의 경우 100억 번의 원소를 다뤄야하기 때문에 풀 수 없습니다. 

아무튼 방법은 간단합니다. 각 고릴라의 이름에 대응하는 우선순위 큐를 만들어주고, 각 쿼리에 대해 그대로 구현해주면 되는데, 이때 우선순위의 크기 보다 많이 빼내야 할 때 주의하면 됩니다.

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

map<string, priority_queue<int> >mp;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q; cin >> q;
	ll ans = 0;
	while (q--) {
		int cmd; cin >> cmd;
		if (cmd == 1) {
			string name; int k;
			cin >> name >> k;

			while (k--) {
				int c; cin >> c;
				mp[name].push(c);
			}
		}
		else {
			string name; int b;
			cin >> name >> b;
			while (!mp[name].empty() && b--) {
				ans += mp[name].top();
				mp[name].pop();
			}
		}
	}
	cout << ans << "\n";
	return 0;
}