[프로그래머스 Level.3] 단속 카메라 - 그리디

문제 - 단속 카메라

시작 지점 기준

1. 차량의 경로를 시작 지점을 기준으로 오름차순으로 정렬합니다.
   

2. 처음 카메라를 설치할 때, 현재 카메라가 커버하지 못하는 구간이면 새로운 카메라를 설치합니다.
   

3. 이미 카메라가 설치된 구간과 현재 구간을 비교하여 최소값으로 업데이트합니다.
   

4. 모든 차량 경로에 대해 위 과정을 반복하며 설치된 카메라의 수를 세고 반환합니다.

종료 지점 기준

1. 차량의 경로를 종료 지점을 기준으로 오름차순으로 정렬합니다.
   

2. 처음 카메라를 설치할 때, 현재 카메라가 커버하지 못하는 구간이면 새로운 카메라를 설치합니다.
   

3. 모든 차량 경로에 대해 위 과정을 반복하며 설치된 카메라의 수를 세고 반환합니다.
   

소스코드

package programmers.level3.sol42884;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 프로그래머스 Level.3 단속 카메라 - 그리디
 * https://school.programmers.co.kr/learn/courses/30/lessons/42884
 */
public class Solution {

    // 시작 지점을 기준으로 카메라 설치
    public int startSolution(int[][] routes) {
        // 시작 지점을 기준으로 정렬
        Arrays.sort(routes, Comparator.comparingInt(o -> o[0]));

        int answer = 0; // 설치된 카메라의 수
        int e = Integer.MIN_VALUE; // 현재 설치된 카메라의 위치

        for (int[] route : routes) {
            // 현재 카메라가 커버하지 못하는 구간이면 새로 카메라 설치
            if (e < route[0]) {
                answer++;
                e = route[1];
            } else {
                // 현재 구간의 끝 지점과 비교하여 최소값으로 업데이트
                e = Math.min(e, route[1]);
            }
        }

        return answer;
    }

    // 종료 지점을 기준으로 카메라 설치
    public int endSolution(int[][] routes) {
        // 종료 지점을 기준으로 정렬
        Arrays.sort(routes, Comparator.comparingInt(o -> o[1]));

        int answer = 0; // 설치된 카메라의 수
        int e = Integer.MIN_VALUE; // 현재 설치된 카메라의 위치

        for (int[] route : routes) {
            // 현재 카메라가 커버하지 못하는 구간이면 새로 카메라 설치
            if (e < route[0]) {
                answer++;
                e = route[1];
            }
        }

        return answer;
    }
}