[Lv.3] 단속카메라-자바

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<Route> routeList=new ArrayList<>();
        for (int[] route : routes) {
            routeList.add(new Route(route[0],route[1]));
        }
        Collections.sort(routeList);
        
        int nowEnd=routeList.get(0).end;
        answer++;
        for (int i = 1; i < routeList.size(); i++) {
            Route target=routeList.get(i);
            if(target.start>nowEnd){
                //need camera
                answer++;
                nowEnd= target.end;
            }
        }
        return answer;
    }
    class Route implements Comparable<Route>{
        int start,end;

        public Route(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Route o) {
            int dis=this.end-o.end;
            if(dis==0){
                return this.start-o.start;
            }
            return dis;
        }
    }
}

탐욕법으로 풀 수 있는 문제다.

카메라의 감지 범위가 없기에 차량이 카메라가 설치된 지점을 지나기만 하면 감지할 수 있다.

차량이 빠져나가는 지점을 기준으로 정렬하고 첫 차량의 출구 지점에서 카메라를 설치한 후(최소 1대의 차는 존재하므로)

나머지 지점에 대해 카메라 설치 여부만 판단하면 된다.

카메라 설치 여부 또한, 현재 타겟 차량이 가장 최근에 설치된 카메라의 감지 범위 밖이라면 해당 차량의 출구 지점에 새로운 카메라를 설치하면 되는 것이다.

직전에 좀 어려운 문제를 풀어서 그런지 상당히 쉽게 푼 문제다.