단속카메라

문제 링크

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 - 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

풀이

나는 이 문제를 스스로 풀지 못했다. 다른 사람의 답을 베꼈으며, 이해를 바탕으로 풀이를 기술한다.

차량들의 진입, 진출 지점이 있다.

위의 입출력 예를 도식화하면 다음과 같다.

-20 ------------------------------------ 15
        -14 ------ -5
    -18 ---- -13
                  -5 ---- -3

이 차량의 경로들을 가지고 카메라 설치 위치를 어떻게 구할까?

나의 경우 진입 지점을 오름차순으로 정렬하여 어떻게 구할지 한참 생각하다가 포기했다.

그러나 진출 지점을 오름차순으로 정렬할 경우 한결 생각하기 쉽다.

이에 대한 로직은 다음과 같다.

1. 차량 경로들을 진출 지점에 대한 오름차순으로 정렬한다.
2. 카메라가 하나도 없는 상태에서는 첫 번째 경로의 진출 지점에 카메라를 설치한다.
3. 각 차량을 순회하며 설치된 각각의 카메라에 대해 다음 차량 경로의 진입 지점 <= 카메라 <= 진출 지점 이 false 경우 해당 진출 지점에 카메라를 추가 설치한다.

이 로직을 바탕으로 카메라를 설치할 경우 다음과 같다

    -18 ---- -13
        -14 ------ -5
                  -5 ---- -3
-20 ------------------------------------ 15
             (cam)       (cam)

이 로직을 구현하기 위해서, 카메라 배열을 만들고 매 차량 경로에 대해서 카메라 배열을 순회하며 확인하는 방법도 있다.

const cameras = [];

routes.forEach(([진입, 진출]) => {
  cameras.forEach(cam => {
    if (!(진입 <= cam && cam <= 진출)) {
      cameras.push(진출);
    }

  })
})

return cameras.length;

그러나 이 경우 routes의 순회가 후반부를 향할 수록 camera에 대해 불필요한 초반부 순회가 이뤄짐을 알 수 있다.

즉 위의 경우 네 번째 route를 돌 때는 첫 번째 카메라를 순회할 필요가 없다.

다르게 생각하면, 카메라의 개수만 따로 합산하고, 마지막 카메라의 위치만 알고 있어도 된다는 뜻이다.

이를 구현하면 다음과 같다.

function solution(routes) {
    var answer = 0;

    routes.sort((a, b) => a[1] - b[1]);

    let min = Number.MIN_SAFE_INTEGER;

    routes.forEach(([enter, out]) => {
        if (min < enter) {
            min = out;
            answer++;
        }
    })

    return answer;
}