단속카메라 자바스크립트

HyosikPark·2020년 12월 12일
0

알고리즘

목록 보기
61/72
function solution(routes) {
    let answer = 1;
    
    routes.sort((a,b) => a[1]-b[1]);
    
    let camera = routes[0][1];
    for(let i = 1; i <routes.length; i++) {
        if(camera < routes[i][0]) {
            answer++;
            camera = routes[i][1];
        }
    }
    return answer;
}

한번의 반복문으로 해결 할 수 있는 코드.
처음에는 dfs나 splice로 해결해보려고 했으나 효율성에서 막히고 말았다.

원리

먼저 차량이 고속도로에서 빠져나가는 지점을 기준으로 오름차순 정렬한다.

단속카메라의 위치를 가장먼저 빠져나가는 차량의 지점에 설치하고 루프를 돌면서 카메라의 지점보다 고속도로를 진입하는 차량의 지점이 더 크다면 그 차량이 빠져나가는 지점에 카메라를 설치한다.

참고

https://kyun2da.github.io/2020/07/20/checkCamera/

0개의 댓글