문제

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 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

---

첫번째 풀이 (오답)

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes, Comparator.comparingInt(a -> a[0]));
        
        int min = routes[0][1];
        int len = routes.length;
        
        for (int i = 1; i < len; i++){
            if (routes[i][0] > min){
                answer++;
                min = routes[i][1];
            }
                
        }
        
        return answer;
    }
}

다틀림.
왜 제 코드는 답이 아닌가요?

이 문제를 해결하기 위해서는 모든 차량이 카메라를 만나도록 하려면, 차량이 고속도로를 나가는 시점들 중 최소 지점에 카메라를 설치하는 것이 중요한 전략입니다. 사용자님의 코드를 보면, 정렬된 routes 배열에서 차량이 고속도로에 진입하는 지점을 기준으로 고려하고 있으며, min을 첫 번째 차량이 고속도로를 나가는 지점으로 설정하고 있습니다. 그러나 이후 차량들이 고속도로에 진입하는 지점과 min을 비교하여 다음 카메라를 설치해야 할 지점을 결정하고 있죠.

이때 주요한 힌트는, 카메라를 설치할 때 마다 min 값을 갱신할 필요가 있는데, 이 min 값은 현재 고려하고 있는 차량들의 고속도로에서 나가는 지점 중 가장 작은 값을 선택해야 합니다. 즉, 모든 차량이 해당 카메라를 만날 수 있는 최소한의 지점을 선택하는 것입니다. 하지만 사용자님의 코드에서는 새로운 min값으로 다음 차량의 고속도로을 나가는 지점을 바로 사용하고 있습니다. 이 로직에서는 차량이 나가는 지점들 중 최소값을 고려하지 않고 바로 지정하기 때문에, 실제로는 더 적은 수의 카메라로도 모든 차량을 단속할 수 있는 경우를 놓치게 됩니다.

따라서 min 값을 갱신하는 방식을 재검토하여, 고려 중인 차량들 중 고속도로에서 나가는 지점이 가장 작은 값을 어떻게 효과적으로 결정할지에 대해 생각해보실 필요가 있습니다.

! 이해완 !

정렬을 시작점으로 하고 있기 때문에, 처음에는 올바른 위치의 카메라가 설치 될 지 몰라도, 그 이후는 최적의 카메라 설치가 불확실!

---

수정 코드 (정답!)

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes, Comparator.comparingInt(a -> a[1]));
        
        int min = routes[0][1];
        int len = routes.length;
        
        for (int i = 1; i < len; i++){
            if (routes[i][0] > min){
                answer++;
                min = routes[i][1];
            }
                
        }
        
        return answer;
    }
}

사실상
Arrays.sort(routes, Comparator.comparingInt(a -> a[0]));를
Arrays.sort(routes, Comparator.comparingInt(a -> a[1]));로 변경해주어 구간이 겹칠 수 있는 부분을 끝나는 지점 기준으로 찾을 수 있게 됨!