[프로그래머스] 단속카메라 (Java)

프로그래머스 단속카메라

문제풀이

자동차가 이동하는 동안 단 한 차례만 단속카메라를 통과하면 된다. 따라서 그리디하게 자동차의 주행 구간이 가장 많이 겹치는 지점에 단속카메라를 설치하면 된다.

• 자동차의 주행 구간을 진입점을 기준으로 오름차순으로 정렬한다.
• 현재 설치 예정 구간(겹치는 구간)과 자동차의 주행 구간을 비교해 설치 예정 구간을 통과하는지 확인한다.
  • 통과한다면 설치 예정 구간을 완벽하게 겹치는 구간으로 갱신한다.
  • 통과하지 않는다면 단속 카메라를 늘리고 새로운 설치 예정 구간(현재 자동차의 주행구간)으로 갱신한다.

구현코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        
        Arrays.sort(routes, new Comparator<int[]>(){
           @Override
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        
        int min = routes[0][0];
        int max = routes[0][1];
        for(int i = 1 ; i < routes.length ; ++i){
            int in = routes[i][0];
            int out = routes[i][1];
            
            if(in > max || out < min) {
                answer++;
                min = in;
                max = out;
            } else {
                min = in > min ? in : min;
                max = max > out ? out : max;
            }
        }
        
        return answer;
    }
}