99클럽 코테 스터디 17일차 TIL: [프로그래머스] 단속카메라

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

프로그래머스

 

그리디로 풀 수 있는 문제였다.

• 최대한 적은 수의 카메라를 설치하기 위해서는 각 자동차가 위치한 범위 내에서 최대한 뒤쪽에 카메라를 설치하면 된다. 그래야 다음 자동차도 이미 설치된 카메라 범위에 포함될 가능성이 있기 때문이다. 즉, 당장에 가장 좋은 것을 선택(= 가장 뒤에 카메라를 설치) 한다는 점에서 그리디 알고리즘이다. 
• 위 아이디어를 가지고 구현하면 되는데, 자동차가 고속도로를 나간 시점을 기준으로 오름차순 정렬을 해야 한다. 처음에는 고속도로에 들어온 시점을 기준으로 정렬해야 한다고 생각했는데, 다음 그림을 보면 고속도로를 나간 시점을 기준으로 정렬해야 한다는 것을 알 수 있다.
  • 첫번째 자동차의 가장 끝 점에 카메라를 설치하게 되는데 고속도로에 들어온 시점을 기준으로 정렬할 경우, 그 다음 자동차가 첫번째 자동차보다 먼저 끝나면 해당 자동차는 카메라의 범위에 포함되지 않는다. (아래 사진의 위 그림) 
  • 따라서 고속도로를 나간 시점을 기준으로 정렬해야 한다. (아래 사진의 아래 그림)

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        
        // 끝나는 시간이 이른 순으로 정렬 
        Arrays.sort(routes, (o1, o2) -> {
           return o1[1] - o2[1]; 
        });
      
        int last = routes[0][1];
        int answer = 1;
        for (int i = 1; i < routes.length; i++) {
            int start = routes[i][0];
            if (start <= last) {
                continue;
            } 
            last = routes[i][1];
            answer++;
        }
        
        return answer;
    }
}