[pro] 프로그래머스 level3 42884 단속카메라 (Java) - 그리디

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

 

[풀이]

먼저 차량이 고속도로를 나간 지점을 기준으로 오름차순 정렬한다. (카메라가 설치되어야 하는 지점)

만약 카메라 설치 위치가 현재 route의 진입지점보다 작다면 카메라를 진출 지점으로 옮겨 설치하도록 하고, 더 크다면 현재 route가 단속카메라를 이미 만날 수 있기 때문에 다음 route로 넘어간다. 

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        //모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return
        //종료지점 오름차순 정렬
        Arrays.sort(routes, new Comparator<int[]>(){
            @Override
            public int compare(int[] r1, int[] r2){
                return r1[1]-r2[1];
            }
        });
        
        int pos = Integer.MIN_VALUE;
        for(int[] r:routes){
            if(pos<r[0]){
                pos = r[1];
                answer++; //카메라 설치
            }
        }
        return answer;
    }
}