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

문제

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

접근법

접근방법이 떠오르지 않아 다른 분의 코드를 참고했다.

풀이

우선 코드를 보고 이해해보자.

function solution(routes) {
    let answer = 0;
    routes.sort((a,b)=>a[1] - b[1]); 
    let cur = -30001;
    
    for(const [IN,OUT] of routes){
        if(cur <= OUT) {
            if(cur >= IN) continue;
            else {
                cur = OUT;
                answer++;
            }
        }
    }
    
    return answer;
}

우선 cur은 카메라를 놓을 위치다. 그리고 for문으로 routes의 첫번째 차량의 진입/진출 지점부터 하나씩 확인한다.
현재 routes는 진출 지점을 기준으로 오름차순 정렬된 상태이기 때문에 진출 지점이 가장 낮은 원소가 맨 앞으로 온다.

그리고 cur이 현재 차량의 진출지점(OUT)보다 작거나 같은지 확인한다.

 if(cur <= OUT) {
 	...
 }

만약 참일 경우 아래와 같은 형태일 것이다.
(cur이 처음에 $-30001$로 초기화 되있다는 사실은 차치하고 로직이 어떤 흐름으로 돌아가는지부터 확인해보자)

그리고 여기서 두 가지 경우로 나눠진다.
1. cur이 현재 차량의 진입지점(IN)보다 크거나 같은 경우
2. cur이 현재 차량의 진입지점(IN)보다 작은 경우

1번

우선 첫 번째 경우부터 보자. cur이 현재 차량의 진입지점(IN)보다 크거나 같은지 확인한다.

if(cur >= IN) continue;

만약 참일 경우 아래와 같은 형태일 것이다.

위와 같은 경우에는 cur에 있는 카메라만으로도 현재 차량을 단속할 수 있다. 따라서 카메라를 추가로 설치하지 않고 다음 차량으로 넘어간다.

2번

그렇지 않고 만약 cur이 IN보다 작다면 아래와 같은 형태일 것이다.

else {
  cur = OUT;
  answer++;
}

위와 같은 경우에는 cur에 있는 카메라로 현재 차량을 단속할 수 없다. 따라서 카메라를 현재 차량의 진출지점(OUT)에 추가 설치한다. 이럴경우 카메라의 개수가 증가했으므로 answer를 1 증가시킨다.

여기까지 이해했다면 핵심 로직을 이해한 것이다.
추가로 다음 차량까지 확인해보자.

첫 번째 차량이 $IN \le cur \le OUT$인 상태에서 아래 그림처럼 두번째 차량의 IN과 OUT이 cur보다 큰 경우, 다시말해 1번의 상태에서 2번의 경우를 마주한 경우를 살펴보자.

이 경우에는 두 번째 차량은 단속할 수 없기 때문에 카메라를 OUT2의 위치에 추가해야 한다. 위에서 본 2번과 같은 방식으로 처리하면 된다.

1번 상태에서 또다시 1번의 경우를 마주한 경우도 위에서 살펴본 1번 방식처럼 추가로 카메라를 설치하지 않아도 1,2번 차량 모두 단속할 수 있다.

진출 지점에 카메라를 설치하는 이유

문제에서는 카메라를 가장 적게 사용하고자 한다. 이는 하나의 카메라가 되도록 많은 차량을 단속하도록 하라는 뜻이고, 되도록 많은 차량을 단속하기 위해서는 차량들의 진출지점(OUT)에 카메라를 설치해야 차량의 경로가 최대한 많이 겹치기 때문에 적은 카메라 수로 되도록 많은 차량을 단속할 수 있다.

• 진입 지점에 카메라를 설치할 경우
  

• 진출 지점에 카메라를 설치할 경우
  

정렬을 수행하는 이유

정렬을 수행하지 않을 경우 카메라가 앞에서부터 설치되지 않기 때문에 제대로된 결과가 나오지 않을 수도 있다.
예를 들어 routes = [[0, 5], [1, 2], [3, 4]] 라고 가정해보자.

정렬을 수행하지 않는 경우

정렬을 수행하지 않는 경우 진출지점 $5$에 카메라가 먼저 설치되며 cur = 5가 된다.
그 후에 차량 두 대의 진입/진출지점 [1,2], [3,4]를 확인하지만 cur이 다른 차량의 진출지점보다 크기 때문에 조건문을 수행하지 않는다.
그림으로 보면 아래와 같은 순서로 진행된다.



따라서 답은 1이 나온다.
하지만 5번 위치에 카메라를 설치할 경우 첫 번째 차량만 단속할 수 있기 때문에 정답이 아니다.
모든 차량을 단속하려면, 2번,4번 위치에 카메라를 설치해야되기 때문에 정답은 2가 나와야 한다.

정렬을 수행한 경우

정렬을 수행한 경우에는 2번,4번 위치에 카메라를 설치함으로써 올바른 정답이 나온다.

전체 코드

function solution(routes) {
    let answer = 0;
    routes.sort((a,b)=>a[1] - b[1]); 
    let cur = -30001;
    
    for(const [IN,OUT] of routes){
        if(cur <= OUT) {
            // IN <= cur <= OUT일 경우
            if(cur >= IN) continue;
            else {
                // 카메라를 새로운 진출지점에 설치
                cur = OUT;
                answer++;
            }
        }
    }
    
    return answer;
}