<Algorithm> 170. 단속카메라(Programmers)

1. 단속카메라(Programmers)

   사용 알고리즘 :  그리디

• 구현코드는 간단하지만 접근하기가 어려웠던 문제, 확실히 그리디 문제는 많이 풀어봐야 접근 방법이 눈에 보일 것 같다.

문제에 대한 접근&생각

1. 각각의 자동차에 대한 범위가 주어짐 -> 정렬?
2. 단속카메라를 최소로 설치해 모든 자동차를 커버할 수 있는 경우 -> 위치는 여러곳이 될 수 있음 -> 최적의 선택 -> 그리디

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

import java.util.Arrays;   class Solution {     public static void main(String[] args) {         System.out.println(solution(new int[][]{{-20,15}, {-14,-5}, {-18,-13},{-5,-3}}));     }     public static int solution(int[][] routes) {         int answer = 0;         /****************************          * 경로를 왼쪽 기준으로 정렬을 하고          * 첫번째 자동차의 끝범위부터 시작하여          * 다음 자동차의 앞부분과 비교하고          * 이전 끝범위가 다음 앞범위에 포함되는지          * 안되는지 그리고 포함되면 이전 끝범위가          * 다음 앞범위를 포함하는지 안하는지를           * 판단하여 최적의 카메라 대수를 구한다.          ****************************/         Arrays.sort(routes, (r1,r2)-> Integer.compare(r1[0], r2[0]));         //Arrays.stream(routes).forEach(i->System.out.println(Arrays.toString(i)));         int front_tail = routes[0][1];                  for(int i = 1; i < routes.length; i++) {             int next_head = routes[i][0];              int next_tail = routes[i][1];                         if(next_head <= front_tail) {                if(front_tail >= next_tail) {                    front_tail = next_tail;                }            }else {                front_tail = next_tail;                answer++;            }        }         return answer+1;     } }     Colored by Color Scripter

cs