설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
입출력 예
routes | return |
---|---|
[[-20,15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
이런 문제는 보통 최적의 해를 구할 때,
단속 카메라를 맨 왼쪽에 붙이든가, 맨 오른쪽에 붙여보면 감이 잡힙니다.
근데 상식적으로 최대한 오른쪽에 설치해야 최적의 해가 보장된다는 걸 직관적으로 알 수 있을 겁니다.
그래야 최대한 많은 차량을 감시할 수 있을테니까요.
제가 풀이한 방식은 이렇습니다.
function solution(routes) {
let ans = 0;
let last_position = -30001; // 마지막으로 설치한 단속 카메라 위치
// 1. 차량들을 고속도로에서 나간 지점을 기준으로 오름차순 정렬합니다.
routes.sort((a, b) => a[1] - b[1]);
// 2. 앞에서부터 보며, 단속 카메라가 없는 구간을 만나면 해당 차량이 나간 지점에 단속 카메라를 설치합니다.
routes.forEach((route) => {
if (route[0] > last_position) {
last_position = route[1];
ans++;
}
});
return ans;
}