단속카메라.md

단속 카메라

문제 링크

문제 설명

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 해라.

입출력 예시

Input: 
    routes : [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	
Output: 2

문제 풀이

먼저 진입시점 기준으로 모든 경로를 정렬해준다. 그 상태에서 그림을 그려보면 해답이 쉽게 보인다. 자동차들이 겹쳐있는 시점 그래서 하나의 cctv설치 만으로 많은 route를 커버할 수 있는 지점은 어디인가. 먼저 진입시점이 빠른 경로를 하나 꺼내서 해당 경로의 끝시점 minPoint라는 변수에 기억한다. 그 후 해당 경로의 끝 지점 보다 더 빨리 끝나는 지점이 나온다면 minPoint값을 해당 끝지점으로 업데이트 시켜준다. 만약 시작시점이 minPoint 보다 큰 경로가 나오면 그 구간부터는 cctv하나로 해결되지 않는 구간이다. 직전 minPoint에 CCTV를 설치하면 이전 모든 경로들이 케어가 되므로 이전구간은 신경쓰지말고 cctv 카운트 1을 올려준다. 새로운 구간에 끝시점에 맞춰 minPoint를 업데이트 해준다. 위 과정을 반복한다.

풀이 코드 JavaScript

function solution(routes) {
    routes.sort( (a , b) => a[0] - b[0])
    const check = new Array(routes.length - 1).fill(false);
    let count = 0;
    let minPoint = Number.MAX_SAFE_INTEGER;
    let i = 0;
    for(const [start, end] of routes){
        
        if(start > minPoint ){
            count++;
            minPoint = end;
        }
        if(end < minPoint){
             minPoint  = end;
        }
    }
    count++; // 마지막 cctv는 반복문 안에서 처리하지 않고 나온다.
    return count;
}