풀이방법
- 진출지점으로 배열을 오름차순 정렬한다.
- 첫번째 차의 진출지점에는 무조건 카메라가 있어야 한다.
- 다음차들부터는 진입지점이 이전 차의 진출지점 이하일 경우에는 제거한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iostream>
using namespace std;
bool compare(vector<int> &a, vector<int> &b) {
if (a[1] < b[1]) {
return true;
} else {
return false;
}
}
int solution(vector<vector<int>> routes) {
int answer = 0;
sort(routes.begin(), routes.end(), compare);
list<vector<int>> carList(routes.begin(), routes.end());
int curCarEndPosition;
while (!carList.empty()) {
curCarEndPosition = carList.front()[1];
carList.pop_front();
int checkCount = carList.size();
list<vector<int>>::iterator iter = carList.begin();
int count = 0;
for (iter=carList.begin(); iter!=carList.end();) {
auto value = *iter;
if (value[0] <= curCarEndPosition) {
iter = carList.erase(iter);
} else {
iter++;
}
}
answer++;
}
return answer;
}
Comments powered by Disqus.