- 문제설명
- 풀이코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector<vector<int>> routes) {
int answer = 1;
int n = routes.size();
sort(routes.begin(),routes.end());
int front = routes[0][1];
for(int i=0;i<n-1;i++){
if(routes[i][1]<front) front = routes[i][1];
if(routes[i+1][0]>front){
answer++;
front = routes[i+1][1];
}
}
return answer;
}
|
cs |
- 시간복잡도
O(nlogn)
- 남의 풀이와 비교
정렬을 하면 진입한 지점이 빠른 순으로 정렬이 된다. 맨 처음 진입한 차의 나간 지점을 기준으로 시작한다. 다음 차량의 나간 지점이 기준 점보다 작으면 카메라가 커버할 수 있는 구간을 줄인다. 또 다음 차량의 진입 지점이 현재 카메라 커버지점에 벗어나면 카메라가 한대 더 필요하므로 카메라 대수를 늘려주고, 해당 차의 나간 지점을 다시 커버리지로 설정한다. 다른 사람들도 거의 같은 방식으로 풀었음을 확인 했다.
- Reference
