[알고리즘] 프로그래머스 - 단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884

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

제한사항

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

어려웠던 점

• 그리디 문제이기 때문에 주어진 배열을 정렬해야한다. 그런데 이 문제는 어떤 값을 기준으로 정렬할지 감이 잘 잡히지 않았다.
• 경로가 겹쳐지는 것을 어떤 방식으로 표현해야 할 지에 대한 어려움이 있었다.

function solution(routes){
    routes.sort((a,b) => a[0] - b[0]);
    let count_cam = 1; // 차가 1대이상은 무조건 있기떄문에
    let flag = routes[0][1];
    for(let i = 0; i < routes.length ; i++){
        if(flag >= routes[i][0]){
             flag = Math.min(flag, routes[i][1]);
        }else{
            count_cam++;
            flag = routes[i][1];
        }
    }
    
    return count_cam;
}

그림을 그려서 문제를 풀어봤는데

1. routes 각 배열의 0번째 index를 기준으로 오름차순 정렬한다.
2. flag에 routes[0][1]값을 저장한다.
3. routes의 길이만큼 for문을 돌면서 각 index에대한 처리를 해주는데,
   3-1. 만약 flag보다 routes[i][0](자동차가 들어가는 시점)가 작거나 같을때는 겹쳐지는 부분이 있다고 판단해, flag에 flag와 routes[i][1]중 더 작은값을 넣어준다.
   3-2. flag보다 routes[i][0](자동차가 들어가는 시점)가 클때는 겹쳐지는 부분이 없는 것이기 때문에 count_cam에 1을 더하고 flag의 값을 수정한다.
4. count_cam이 1로 초기화된 이유는 자동차가 적어도 1대는 들어오기 때문이다!!