[C++]BOJ 1202 - 보석 도둑

처음엔 무식하게 2중 for문으로 돌려보았다.
맞겠지 싶었는데 시간초과가 떴다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
p b[300001];
int c[300001];
bool com(const pair<int, int>& a, const pair<int, int>& b)
{
	if(a.first == b.first) return a.second > b.second;
	return a.first > b.first;
}
int main() {
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> b[i].second >> b[i].first;
	}
	for(int i = 0; i < k; i++) {
		cin >> c[i];
	}
	sort(b, b + n, com);
	sort(c, c + k);
	int total = 0;
	for(int i = 0; i < k; i++) {
		for(int j = 0; j < n; j++) {
			if(c[i] >= b[j].second) {
				total += b[j].first;
				b[j].second = INT_MAX;
				break;
			}
		}
	}
	cout << total;
}

시간초과가 떴기 때문에 논리가 맞고 틀리고는 모르지만 맞다고 생각하기로 했다.


생각해보니 n과 k가 300,000이라 가정했을 때 최악의 경우 2중 for문에서 300,000^2 번 연산하므로 제한시간 1초는 터무니없었다.


구글링해보니 우선순위 큐를 사용하더라
우선순위 큐를 얕게 핥아봤다.


우선순위 큐는 비선형자료구조로써 넣은 순서와 상관없이 우선순위대로 나간다.


max heap의 형태로 원소들이 저장되어 있다고 한다.
굉장한 우연으로 이거 풀기 전에 힙 정렬을 공부하고 왔다.

위 코드를 변형해서 우선순위 큐가지고 짜봤다.

1. 보석과 가방을 무게기준으로 오름차순 정렬한다.
2. 가방 무게가 작은 것부터 for문을 돌며 그 가방에 들어갈 수 있는 보석을 우선순위 큐에 넣는다.
3. 가장 큰 요소를 큐어서 빼서 total에 더한다.
4. 반복한다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
priority_queue<int> pq;
p b[300001];
int c[300001];
int main() {
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> b[i].first >> b[i].second;
	for(int i = 0; i < k; i++)
		cin >> c[i];
	sort(b, b + n);
	sort(c, c + k);
	long long total = 0;
	int j = 0;
	for(int i = 0; i < k; i++) {
		while(j < n && b[j].first <= c[i])
			pq.push(b[j++].second);		
		if(!pq.empty()) {
			total += pq.top();
			pq.pop();
		}
	}
	cout << total;
}

맞았다.