[Programmers] 단속카메라 (Lv 3, JavaScript)

[ 개요 ]
그리디

[ 학습 내용 ]
그리디에서 가장 많이 본 유형의 문제가 아닌가 싶다.

여러구간이 존재하고, 그 구간이 겹치는 곳에 최소한의 무언가를 설치한다는 내용을 포함한 그리디 문제

이 문제를 해결하기 위해 다음의 경우를 항상 외워두도록 했다.

 

1) 구간에 대해 오름차순 할것

2) 첫 구간의 끝을 기억하고 배제한 뒤 시작할 것

3) 다음구간과 비교할 때 다음을 판단할 것

    3-1) 내 기준끝점이, 현재 구간의 시작점보다 작은가?

        → 결과가 추가되어야 하며(현 문제에서는 카메라) 내 기준끝점을 현재구간의 끝점으로 변경한다

    3-2) 내 기준끝점이, 현재 구간의 끝점보다 큰가?
        → 내 기준끝점을 현재구간의 끝점으로 변경한다

 

※ 위 두 경우에 현재구간의 끝점으로 변경하는 이유는 다음구간과 비교하기 위해서 변경해야한다.

※ 3-1/3-2를 만족하지 않는 경우, 기준으로 잡은 구간에 현재구간이 포함되는 구간이므로 신경쓰지 않아도된다.

[ 소스 코드 ]

function solution(routes) {
    let camera = 1;
    routes.sort((o1, o2) => o1[0] - o2[0]);
    
    let out = routes[0][1];
    routes.shift();
    routes.forEach((route) => {
        if (out < route[0]) {
            camera++;
            out = route[1];
        }
        
        if (out > route[1]) {
            out = route[1];
        }
    })
    return camera;
}