[프로그래머스 알고리즘] 단속카메라 (level 3)

문제

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

과정

이 문제는 그리디 알고리즘으로, 특정 조건을 만족하는 최대/최소를 구하는 문제에 해당한다. 그리고, 값이 될 수 있는 범위가 생긴다. 그리디 알고리즘은 보통 어떤 값을 정렬한 후 풀면 쉽게 풀리는데, 이 문제에서 정렬할 수 있는 기준은
1. 시작 위치
2. 끝나는 위치
3. 길이
가 있다. 그 중 이 문제는 끝나는 위치를 기준으로 오름차순 정렬한 후 문제를 해결하였다.

끝나는 위치 기준 정렬

Arrays.sort(routes, new Comparator<int[]>(){
	@Override
    public int compare(int[] route1, int[] route2){
    	return route1[1] - route2[1];		//끝나는 지점 기준 오름차순 정렬
    }
}

풀이 로직

끝나는 지점을 기준으로 오름차순 정렬했기 때문에, 마지막 캠의 위치가 현재 탐색중인 경로의 시작 위치보다 크면 그 캠의 위치가 현재 경로에도 적용된다.

코드

import java.util.*;
//
class Solution {    //모든 경로에 단속 카메라 걸리게 하는데, 카메라 놓는 최소 갯수 
    public int solution(int[][] routes) {
        int answer = 0;     
//        
        Arrays.sort(routes, new Comparator<int[]>(){
            @Override
            public int compare(int[] route1, int[] route2){
                return route1[1] - route2[1];       //끝나는 지점 기준 오름차순 정렬
            }
        });
//        
        int camLoc = Integer.MIN_VALUE;
//        
        for(int i = 0; i < routes.length; i++){     //차의 갯수만큼 반복 
            if(camLoc < routes[i][0]){              //마지막 캠의 위치가 현재 차의 시작위치보다 작으면 하나 설치 
                answer++;
                camLoc = routes[i][1];
            }
        }
//            
        return answer;      //캠 갯수
    }
}