단속카메라 surveillance camera

💡

Level 3 210925 https://programmers.co.kr/learn/courses/30/lessons/42884

문제 설명

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

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

제한사항

차량의 대수는 1대 이상 10,000대 이하입니다.

routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.

차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.

차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes

return

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

입출력 예 설명

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

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

My solution

중요한 포인트가 배열에 주어진 동선이 겹치지 않는 구간을 어떻게 찾아내느냐였다.

[ [-20, 15], [-20, -15], [-14, -5], [-18, -13], [-5, -3]]) >> 2

[-20, -15], [-18, -13], [-20, 15] 세 개의 동선이 겹쳐지는 구간과

[-20,15], [-18, -13], [-14, -5] 세 개의 동선이 겹치는 구간과

[-20,15], [-14, -5], [-5, -3] 세 개의 동선이 겹치는 구간이 보인다.

이렇게 되면 가장 동선이 많이 겹쳐지는 구간에 캠을 설치하는 것이 답을 도출하는 방법이 아니라는 것을 알 수 있다.

그 다음 생각해볼 수 있는 것은 차량이 맨 처음 도로를 이탈하는 시점마다의 겹치는 차량 동선이 몇 개인지 세보는 것이다.

-15 지점에서 이탈이 발생하면 겹치는 차량이 3개이다. 그런데 다음 설치할 카메라에서는 이미 찍힌 차량의 동선을 계산할 필요가 없다. 이때 겹치는 차량 동선들을 제거해줄 수 있다면, 다음 이탈 지점이 -5가 되고 이 -5라는 위치는 -14와 -5에 진입한 차량의 동선을 제거시킬 수 있다.

그런데 routes 배열에서 원소를 제거하며 만들 수도 있지만 이것은 불필요한 연산이고 더 깔끔한 방법이 있었다.

예를 들어 첫 이탈이 발생한 -15를 캠의 위치로 저장하고 이보다 작거나 같은 진입 시점을 가진 차량의 동선들은 무시해버리는 것이다. 이 값보다 큰 진입시점을 가진 차량의 동선이 들어오게 되면(여기서는 -14에 진입하는 차량 동선) 이 원소부터 캠을 새로 설치할 위치를 업데이트해주는 것이다.

이탈 지점에 맞춰 배열이 정렬되어 있으므로 겹쳐지지 않는 첫 번째 다음 동선을 기준으로 이 차량은 무조건 한 번은 찍혀야하니 이탈 전까지 가능한 한 가장 많은 동선을 커버하도록 이탈 지점에 캠을 설치한 다음 진입시점이 더 작으면 무시하고, 진입시점이 더 커서 겹쳐지지 않으면 그 원소의 이탈 지점을 기준으로 캠을 새로 설치하는 로직을 반복하게 된다.

소스 코드

function solution(routes) {
    let answer = 0;
    let cam = -30000;
    routes.sort((a, b) => {
        if (a[1] === b[1]) return a[0] - b[0];
        else return a[1] - b[1];
    });
    for (let x of routes) {
        // 다음 동선의 진입 시점이 캠의 범위 안이라면 찍고 지나가는 것이니 무시
        // cam을 지나쳐서 진입한다면 캠을 새로 설치할 지점을 업데이트한다. 이 때마다 answer++;
        // 처음에는 -30000이므로 첫 동선의 x[1](이탈지점)이 캠의 위치가 된다.
        if (x[0] > cam) {
            cam = x[1];
            answer++;
        }
    }
    return answer;
}

test("solution", () => {
    expect(
        solution([
            [-20, 15],
            [-14, -5],
            [-18, -13],
            [-5, -3],
        ])
    ).toBe(2);
    expect(
        solution([
            [-2, -1],
            [1, 2],
            [-3, 0],
        ])
    ).toBe(2);
    expect(solution([[0, 0]])).toBe(1);
    expect(
        solution([
            [0, 1],
            [0, 1],
            [1, 2],
        ])
    ).toBe(1);
    expect(
        solution([
            [0, 1],
            [2, 3],
            [4, 5],
            [6, 7],
        ])
    ).toBe(4);
    expect(
        solution([
            [-20, -15],
            [-14, -5],
            [-18, -13],
            [-5, -3],
        ])
    ).toBe(2);
    expect(
        solution([
            [-20, 15],
            [-20, -15],
            [-14, -5],
            [-18, -13],
            [-5, -3],
        ])
    ).toBe(2);
});