C++ 자료구조들에 대하여

그리디 문제를 풀던 도중 vector 의 erase가 O(n) 복잡도로 동작한다는 것을 알았다... 난 너무 그동안 겉핥기 식으로 STL을 써왓던것 같다..

그러므로 삽입 삭제가 빈번하게 일어나는 상황에서 vector의 사용은 시간초과를 도래할 수 있따.. 아래 문제가 vector의 erase 남용으로 틀린 문제와 코드다.

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

1202번: 보석 도둑

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <string>
#include <queue>
using namespace std;
int n, k,c;
vector<int> bag;
pair<int,int> p[300001];
int ans = 0;
int cmp(pair<int,int> a, pair<int,int> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second > b.second;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	for (int i = 0; i < k; i++) {
		int num;
		cin >> num;
		bag.push_back(num);
	}
	sort(p, p + n,cmp);
	sort(bag.begin(), bag.end());
	for (int i = 0; i < n; i++) {
		auto it = lower_bound(bag.begin(), bag.end(), p[i].first);
		if (it != bag.end()) {
			ans += p[i].second;
			bag.erase(it);
		}
	}
	cout << ans;
}

 

검색해보니 set과 map은 삽입, 삭제, 탐색이 O(lgN)의 복잡도이며 위 문제와 같은 경우는 multiset을 사용하면 중복된 값도 같이 다룰수있다. 또한 set은 자체 lower 와 upper bound 함수를 제공한다고 하니 한번 익혀두자. 

아래는 정답코드로 동일한 알고리즘이지만 vector와 multiset의 자료구조 사용 차이뿐이없다.

multiset의 erase()는 삭제 구간의 [시작, 끝) 의 set의 iterator를 기입하면되는데 사실 삭제하고자하는 지점의 iterator 하나만 넣어도 된다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <string>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
ll n, k,c;
multiset<ll> bag;
pair<ll, ll> p[300001];
int cmp(pair<ll, ll> a, pair<ll, ll> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second > b.second;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (ll i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	for (ll i = 0; i < k; i++) {
		ll num;
		cin >> num;
		bag.insert(num);
	}
	sort(p, p + n,cmp);
	ll ans = 0;
	ll _size = k;
	for (ll i = 0; i < n; i++) {
		auto it = bag.lower_bound(p[i].first);
		if (it != bag.end()) {
			ans += p[i].second;
			auto nxt = it;
			nxt++;
			bag.erase(it, nxt);
		}
	}
	cout << ans;
}

아직 안써본 자료구조도 너무많고 공부해야할게 산더미다. 쩝