문제 출처

코딩테스트 연습 > 탐욕법(Greedy) > 단속카메라
https://school.programmers.co.kr/learn/courses/30/lessons/42884

문제 설명

차량의 경로 route[진입][진출]이 주어질 때, 모든 차량이 적어도 한 번은 카메라 만나도록하면 최소 몇 대의 카메라가 필요한지 return 하라.

접근 방법

차량의 진출에 근거하여 풀이한다.
하나의 차량에 진출부분에 카메라를 설치하면 그 부분 전에 진입이 없다면, 카메라를 한 대 더 설치하고, 마지막 카메라 설치 위치를 진출부분으로 바꾼다.

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, Comparator.comparingInt(a -> a[1]));
        
        int lastCameraPosition = Integer.MIN_VALUE;
        
        for(int[] route : routes){
            int entry = route[0];
            int exit = route[1];
            
            if(lastCameraPosition < entry){
                answer++;
                lastCameraPosition = exit;
            }
        }
        return answer;
    }
}

알게된 점

처음 문제를 풀이 할 때, "범위"를 좁혀가면서 가장 많이 해당하는 범위에 카메라를 설치하는 방식으로 접근해야겠다라고 생각했다. BFS를 통해 MIN <= 범위 <= MAX인 부분을 큐에 넣고, 점차 범위를 줄여가는 방식으로 접근했지만, 더 간단하게 "진출"의 범위를 벗어난 "진입"을 가진 차량은 카메라를 하나 더 쓴다는 간단한 방법이 있었다.
(1시간 반 동안 생각해서 풀었지만, 쉬운 방법이 있어 허탈했다.)

import java.util.*;

class Solution {
    static HashSet<int[]> visited;
    static int answer;
    
    public void bfs(int[] start, int[][] routes){
        Queue<int[]> q = new LinkedList<>();
        q.add(start);
        int min = -300000;
        int max = 300000;
        while(!q.isEmpty()){
            int[] point = q.poll();
            visited.add(point);
            for(int i = 0; i<routes.length; i++){
                if(visited.contains(routes[i])) continue;
                if(min <=routes[i][0] || max >=routes[i][0] || min <= routes[i][1] || max >= routes[i][1] ){
                    q.add(routes[i]);
                    min = Math.max(min, routes[i][0]);
                    max = Math.min(max, routes[i][1]);
                }
            }
        }
        answer++;
    }
    public int solution(int[][] routes) {
        answer = 0;
        visited = new HashSet<>();
        Arrays.sort(routes);
        
        for(int i = 0; i< routes.length; i++){
            if(visited.contains(routes[i])) continue;
            bfs(routes[i], routes);
        }
        

        return answer;
    }
}

문제푼 흔적