[프로그래머스 Lv.3] 단속 카메라 (js)

https://programmers.co.kr/learn/courses/30/lessons/42884?language=javascript 

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

function solution(routes) {
    routes.sort((a,b) => a[1]-b[1]);
    
    let camera = 1;
    
    let value = routes.shift()[1];
    
    while(routes.length) {
        if(routes[0][0] <= value && routes[0][1] >= value) {
            routes.shift();
        } else {
            value = routes.shift()[1];
            camera++;
        }
    }
    return camera;
}

 

알고리즘

 

1. 우선 나가는 시간 오름차순으로 정렬해준다.

- 나가는 시간에 카메라에 찍히는 게 전체적으로 봤을 때 가장 유리하며, 그 다음 시간과 최소 차이를 유지할 수 있다.

 

2. 첫 번째 값의 나가는 값을 지정해놓고 while문을 돌린다.

- [ [ -20, -15 ], [ -18, -13 ], [ -14, -5 ], [ -5, -3 ] ]  

 

해당 배열에서 -15값을 value에 넣고, shift해준다.

- [ [ -18, -13 ], [ -14, -5 ], [ -5, -3 ] ], value = -15

 

while문을 돌면서 다음 값이 -15에 위치한 카메라에 찍히는 지(범위에 value값이 있는 지) 확인한다.

만약 찍힌다면 그냥 shift를 이용해 없애준다.

- [[ -14, -5 ], [ -5, -3 ] ], value = -15  // 찍히므로 shift()

   

만약 찍히지 않는다면 value값을 다시 [0][1]로 지정해주고, 해당 값에 카메라를 추가한다.

- [[ -5, -3 ] ], value = -5. 

마지막도 -5에 포함되므로 shift되며 해당 while문이 끝나게 된다.