프로그래머스: 단속카메라(javascript, greedy)

 문제는 쉬우나 처음 접근을 잘못해 헤맨 문제이다. 이전에 호텔방 예약하는 문제와 비슷하여 시작 시간과 끝시간만 비교했으나 다음 차의 범위가 이전 차의 범위안에 들더라도 비교가 계속 되면 과거 차들의 정보가 반영이 안되는 문제를 고려 안했다.

 그 부분을 수정하기 위해 시작 시간과 끝 시간을 계속 변경 시키는 알고리즘을 추가하여 문제풀이에 성공하였다. greedy algorithm은 떠올리기는 쉬우나 그것이 절대해인지 증명하는 것이 매우 어려워 사실상 운에 맡기거나 반례를 열심히 생각해내야 한다..

function solution(routes) {
    let answer = 0;
    routes.sort((a,b)=>a[0]-b[0])
    let start = 30001
    let end = -30001
    routes.forEach(r=>{
        if(start<=r[0] && r[1]<=end){
            start = r[0]
            end = r[1]
        }
        else if(start<=r[0] && r[0]<=end){
            }
        else{
            start = r[0]
            end = r[1]
            answer++
        }
    })
    return answer;
}

 먼저 정렬을 해준다. 정렬을 하면 풀리는 문제가 많다. 투 포인터도 그렇고.. 그리고 start와 end를 각각 문제의 최대범위/최서범위로 한 이유는 첫번째 원소는 무조건 answer를 증가시켜야 하고 forEach에서 index를 값과 함께 받을 수 있지만 그러면 조건문을 사용해서 첫번쨰 원소인지 판별해야 하고 그러면 코드가 우아하지 않기 때문에 굳이 저렇게 풀었다.

 조건문은 각각 새로운 차의 범위가 이전 차의 범위 안에 드는지/ 범위 안에 들진 않지만 시작점은 이전 범위 안에 드는 경우/ 둘다 아닌 경우로 나누어 풀었다.