[C++] 백준 1202번: 보석 도둑

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

1202번: 보석 도둑

 

문제를 풀면서 중요한 개념을 배웠습니다.

중요 포인트

set 라이브러리 활용

upper_bound, lower_bound 개념

그래야 시간복잡도를 최소한으로 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Jewelry
{
	int M;
	int V;
};

bool compareJ(Jewelry a, Jewelry b){
	if (a.V == b.V) return a.M < b.M;
	else
		return a.V > b.V;
}

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

	int N, K, m, v, c;
	cin >> N >> K;
	vector<Jewelry>JewelryList;
	multiset<int>bags;// multiset은 중복이 허용됨 / set은 기본족으로 이진트리 구조임
	long long answer = 0;
	for (int i = 0; i < N; i++) {
		cin >> m >> v;
		JewelryList.push_back({ m,v });
	}

	sort(JewelryList.begin(), JewelryList.end(), compareJ);

	for (int i = 0; i < K; i++) {
		cin >> c;
		bags.insert(c);
	}
	
	for (int i = 0; i < N; i++) {
		auto Bag = bags.lower_bound(JewelryList[i].M);
		//key값에 해당하는 원소가 시작되는 주소를 가리키는 반복자 반환 // upper는 해당원소가 끝나는 다음 주소를 가리킴
		//아래의 경우는 O(N)의 시간복잡도를 위는 O(log(N))의 시간복잡도를 가짐
		//auto Bag = lower_bound(bags.begin(), bags.end(), JewelryList[i].M);
		if (Bag != bags.end()) {
			answer += JewelryList[i].V;
			bags.erase(Bag); // erase(key) : 반복자가 가르키는 원소 제거/O(log(N))의 시간복잡도를 가짐
		}
		if (bags.size() == 0)
			break;
	}

	cout << answer;

	return 0;
}