[Java] 프로그래머스 - 단속카메라

프로그래머스 단속카메라 문제는 모든 차량이 단속 카메라를 만나게 할 수 있는 카메라의 최소 개수를 구하는 문제다. 난이도는 레벨3이며 그리디 알고리즘를 통해 해결할 수 있다.

 

프로그래머스 - 단속카메라 문제 정보

알고리즘 분류

- 그리디

난이도

- Level 3

 

문제 요약

• 각 차량의 고속도로 진입/진출 지점이 주어진다.
• 모든 차량이 적어도 하나의 단속 카메라를 만나게 하려면 필요한 단속카메라의 최소 개수는?

 

문제 풀이 과정

• 진출 지점 기준으로 오름차순 정렬
• 앞에꺼부터, 가장 마지막 카메라 지나면 패스, 안지나면 현재 차의 진출 지점에 카메라 추가

코드

public int solution(int[][] routes) {
    Arrays.sort(routes, (o1, o2) -> {
        if (o1[1] < o2[1]) return -1;
        else if (o1[1] > o2[1]) return 1;
        else return o1[0] - o2[0];
    });

    int ans = 0;
    int lastCamera = -30001;
    for (int[] route : routes) {
        int in = route[0], out = route[1];
        if (in > lastCamera || lastCamera > out) {
            ans++;
            lastCamera = out;
        }
    }
    return ans;
}

• 시간복잡도: 정렬 O(NlogN) + 체크 O(N)
• 공간복잡도: 별도 공간 X