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; //캠 갯수 } }