[프로그래머스] 단속카메라 (javascript)

풀어보러 가기 : https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

 

그리디는 많이 풀어보는 수밖에 없는 것 같다..

나는 구현보다 아이디어를 떠올리기가 더 어려운 것 같다.

 

function solution(routes) {
    var answer = 0;
    // 종료위치 기준으로 오름차순 정력
    routes.sort((a,b) => a[1]-b[1]);
    
    // 카메라의 위치를 최솟값보다 작게 두고 시작한다.
    let cam = -300001;
    for(let i in routes){
        // 차량의 진입점이 현재 카메라보다 뒤에 있다면 나간 지점에 카메라를 설치한다.
        if(cam < routes[i][0]){
            cam = routes[i][1];
            answer++;
        }
    }
    return answer;
}

 

 

---

처음 생각한 풀이방법

[[-20,15],[-14,-5],[-18,-13],[-5,-3],[20,21]]
각 자동차들 경로가 겹치는 구간들을 찾아낸다.
0번 1번 = -14, -5
0번 2번 = -18, -13
0번 3번 = -5, -3
0번 4번 = x(겹치지 않음)
1번 2번 = x
1번 3번 = -5
1번 4번 = x
2번 3번 = x
2번 4번 = x
3번 4번 = x
 => [-14, -5], [-18, -13], [-5, -3], [-5, -5]
아무 구간과도 겹치지 않는 차량이 있다면 카메라를 한대 추가한다.
 => 4번은 아무 구간과도 겹치지 않음, answer=1;
겹치는 구간들이 더 이상 겹치지 않을 때까지 줄여본다.
=> [-14, -13] [-5, -5]
구간의 수를 answer에 더한다. answer=3

처음 생각했을 땐 효율적이라고 생각했는데...

하지만 이 방법은 반복이 너무 많이 필요하고 비효율적인 풀이였다.

 

검색으로 더 나은, 그리고 그리디스러운 방법을 찾아냈다.

 

 

참고 블로그(ahnick님)

굉장히 친절하고 이해하기 쉽게 설명되어 있으니 이쪽을 보는 것이 좋을 것 같다.

https://velog.io/@ahnick/programmers-%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC