[JS] 단속카메라

그리디 알고리즘을 활용하여 해결할 수 있는 문제이다.

 

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

프로그래머스

 

 

사실 이전에 2단계 문제중에서 상당히 유사한 문제가 하나 있던걸로 기억한다. [요격시스템]

 

풀이방법은 아래와 같다.

 

결국 과속카메라를 설치하는 것도 위 그림처럼 만드는 것이다.

 

 

한선분이 있다면 해당 선분은 무조건 포함되어야 한다. 따라서 시작점을 잡으면 그선의 끝점을 잡는다. 이 두점을 A,B라고 두자

다음 선분의 시작점이 B보다 뒤라면 무조건 카메라를 하나 더 설치해야할수밖에 없다. 이 경우 A,B를 갱신시켜준다.

만약 다음선분의 시작점이 B보다 앞이라면 해당 선분으로 커버할 수 있다 단 B보다 선분의 끝점이 짧다면 B점을 갱신시켜줘야 한다.

 

 

1. 우선 route를 시작점에 맞춰서 정렬한다.

2. 시작점이 tmp보다 크다면 tmp를 갱신시켜준다.

3. 선분의 끝이 tmp보다 작다면 tmp를 갱신시켜준다.

 

 

 

풀이는 간단한 문제였다.

 

function solution(routes) {
    routes.sort((a,b) => a[0]-b[0])
    
    let ret = 0
    let tmp = -30001
    for (const [start,end] of routes){
        if(tmp < start) {
            ret ++
            tmp = end
        }
        if(tmp > end) tmp = end
    }
    return ret
}