프로그래머스: 단속카메라

(문제링크)

문제

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

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

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

풀이

모든 차량이 단속 카메라를 만나기 위한 최대 개수는 모든 차량의 수이다.
차량끼리 겹치는 구간이 있다면 카메라 수를 적게 배치해야 최소 개수를 구할 수 있다.

이 겹치는 구간을 알려면?
고속도로에서 나가는 지점이 먼저인 차량부터 정렬한다.
집입하는 지점이 아닌 나가는 지점을 기준으로 하는 이유는?
어떤 차량이 고속도로를 나가기 전에 다른 차량이 진입했는지가 중요하기 때문에 나가는 지점을 기준으로 했다.

1. 나가는 지점이 먼저인 차량부터 정렬
2. 차량이 고속도로에서 나갈 때 다른 차량과 겹치지 않는다면 카메라 수 +1

소스코드

function solution(routes) {
    // 끝나는 지점이 먼저인 것부터 정렬
    routes.sort((a,b) => a[1] - b[1]);
    
    // 끝나는 지점이 지나는 구간에 안 겹쳤다면 카메라++ & 지점 초기화
    let point = routes[0][1];
    let camera = 1;
    for (let i=1; i<routes.length; i++) {
        if (point < routes[i][0] || routes[i][1] < point) {
            point = routes[i][1];
            camera++;
        }
    }
    return camera;
}