탐욕법 - 단속카메라

이 문제는 단속 카메라를 한 번 이상 만나게 하기 위해서는 차량의 경로가 겹치는 부분에 카메라를 최소한으로 설치해야한다. 이때, 경로가 겹치는 부분에 카메라를 설치하면 해당 경로를 통과하는 모든 차량이 카메라를 만나게 된다.

 

문제 풀이

1. routes를 고속도로를 나간 지점을 기준으로 오름차순 정렬

2. routes[0][1]위치에 카메라를 설치

3. 반복문을 통해 routes를 탐색하면서 routes[i][0](시작지점)이 마지막에 설치한 카메라 위치보다 크다면 카메라를 routes[i][1]에 설치한다. 

 

고속도로를 수평선이라 생각하고 그림을 그리면 더 쉬울것이다.

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (o1, o2) -> o1[1] - o2[1]);
        int location = routes[0][1];
        int answer = 1;
        
        for (int i = 1; i < routes.length; i++) {
            if (routes[i][0] > location) {
                answer++;
                location = routes[i][1];
            }
        }
        return answer;
    }
}

 

 

 

총 정리

차량의 경로를 정렬하는데 O(N log N)의 시간이 소요된다. 차량의 경로를 한 번 순회하면서 카메라를 설치하므로 O(N)시간이 소요된다. 따라서 전체 시간 복잡도는 O(N log N) 이다.

진입 지점과 진출 지점을 포함하는 구간을 고려하여, 진출 지점을 기준으로 차량의 경로를 정렬해줘야한다. 진출 지점이 빠른 순서대로 정렬하는 이유는, 가능한 가장 빨리 카메라를 설치하여 이후 차량들이 그 카메라에 걸리도록 하기 위해서이다. 카메라를 설치할 위치는 차량의 진출 지점에 설치해야 나중에 해당 지점을 지나면 그 이후로는 더 이상 카메라에 걸리지 않기 때문이다.