[프로그래머스 (java)] 단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884?language=java 

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

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

해당 문제는 자동차 route 가 추가 됐을때, 계속 최소한의 카메라 개수를 유지하도록 부분적인 최적해를 설계하면 모든 자동차 route 를 추가했을때도 전체적으로 최적해를 구할 수 있습니다.

또한 무제를 쉽게 풀기 위해 다음과 같은 한가지 사실을 반드시 확인해야 합니다.

고속도로에서 먼저 나가는 순서대로 자동차가 추가됐을때 추가된 자동차를 감시할 수 있는 감시 카메라가 존재하지 않는다면, 가능한 뒤에 카메라를 설치하는 것이 무조건 이득이다. 즉 추가된 자동차가 나가는 시점에 카메라를 설치하는 것이 가장 효율적이다. 

왜 그럴까요?

고속도로에서 먼저 나가는 순서대로 자동차를 정렬했다고 생각해봅시다. 

1번부터 10번 자동차까지 감시할 수 있는 카메라가 이미 설치되어있는 상태에서 11번 자동차가 추가됐을때, 11번 자동차를 감시할 수 있는 카메라가 없다고 가정해보겠습니다. 앞으로 뒤에 추가되는 자동차는 11번 자동차보다 같거나 나중에 고속도로에서 나가는 자동차들입니다. 이때 11번 자동차를 감시하기 위한 단속카메라를 굳이 11번 자동차가 진입하는 가장 앞부분에 설치해야할까요?
최대한 뒤에 설치할수록 11번 자동차 다음으로 나오는 자동차들을 감시할 확률이 올라갑니다.

 

위의 그림에서 빨간선이 11번 자동차의 진입과 탈출 

검정선들이 1 ~ 10번 자동차의 진입/탈출, 파란선이 11번 이후 자동차의 진입/탈출  라고 생각하면 쉽게 이해할 수 있습니다. 

위의 규칙을 코드로 작성하면 다음과 같습니다.

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (int[] a, int[] b) -> Integer.compare(a[1], b[1]));
        Stack<Integer> cameraLocation = new Stack<>();
        for (int[] route : routes) {
            if (cameraLocation.isEmpty() || cameraLocation.peek() < route[0]) {
                cameraLocation.push(route[1]);
            }
        }
        int answer = cameraLocation.size();
        return answer;
    }
}