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

# 문제 원문

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]]

2

 

 

# 문제 풀이

 

입력 받은 자동차 경로 routes의 모든 지점을 가장 적은 카메라로 커버 가능한 경우 카메라가 몇개가 들어가는지 찾는 문제이다. 그리디 문제에 해당하며, 솔직히 문제 자체의 엣지케이스가 테스트케이스로 잘 정리가 안되어 있지 않나는 생각이 들었다. 엣지케이스 테스트를 위해서 제출한 것에서 정답이 나와버렸다.

 

# 솔루션 플로우

1. 입력 받은 routes를 정렬한다.

2. 정렬된 routes를 순회하면서 각 요소마다 카메라가 없으면 설치하고 그 갯수를 카운트한다.

3. 카운트한 갯수를 구한다.

4. result를 반환한다.

1. FP

function solution(routes) {
    return routes
        .sort((a, b) => a[1] - b[1])
        .reduce((result, current) => {
            let isCam = false;
            result[0].forEach((cctv) => {
                if (current[0] <= cctv && current[1] >= cctv) {
                    isCam = true;
                } else if (current[0] >= cctv && current[1] <= cctv) {
                    isCam = true;
                }
            });
            if (!isCam) {
                result[1]++;
                result[0].push(current[1]);
            }

            return result;
        }, [[], 0])[1];
}