[프로그래머스] 단속카메라(Java, Greedy, 사고력, Lv3)

programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

 

 

## 접근방법

---

그리디 문제는 항상 코드는 단순하지만, 생각해내기가 쉽지 않다. 이 문제는 최소의 단속카메라를 통해서, 모든 운전자들을 단속할 수 있어야 한다.

 

 

 

어떤 운전자부터 카메라를 배치해야할까? 단속이 안된 운전자중에서, 가장 도착 거리가 작은 운전자를 확인해야 한다. 가장 도착 거리가 작은 운전자도 카메라에 찍혀야 되므로 카메라는 두는 것은 자명하며, 가장 도착 거리가 작은 운전자부터 확인해야 다른 운전자들이 해당 단속카메라로 단속이 된다면, 카메라를 불필요하게 설치할 일이 없다. 즉 문제의 조건인 최소를 의미한다.

 

 

 

이 카메라를 어디에 두어야 다른 운전자들에게 최대한 영향을 줄 수 있을까? 가장 끝 부분에 두어야 다른 운전자들을 단속할 가능성이 증가된다. 도착 거리의 끝에 카메라를 두는 방법이 그리디를 의미한다.

 

 

 

도착 거리가 작은 운전자부터 검사를 해야 하므로, 도착 거리의 정렬이 필요하다. 도착 거리를 정렬한 후에는, 도착 거리보다 작은 출발 지점이 존재하면, 현재 카메라로 단속이 가능하다.

 

 

 

만약에, 도착 거리보다 큰 출발 지점이 나타나면, 새로운 카메라를 도착 거리의 끝에 카메라를 다시 두면 된다.

 

 

 

## 해설코드

---

import java.util.Arrays;
 
class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b) -> (a[1] - b[1]));
        int answer = 1;
        int cam = routes[0][1];
        
        for(int i = 0; i < routes.length; i++){
            if(cam < routes[i][0]){
                cam = routes[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}