[Programmers] 단속카메라

🔒 문제

💡 아이디어

가설1

설치할 때마다 지워지는 경로가 가장 많은 것을 전수조사 해보자
-30,000 ~ 30,000을 보며 매번 route 에서 지워지는 수가 최대인 것을 선택

[연산 횟수] : 60,000 * 10,000 => 6억

=> Backtracking 풀이는 아니겠다.

가설2

출발지점 기준 오름차순으로 route 를 정렬하고 매번 가장 작은 route 의 도착지점을 지우는 것이 가장 적은 카메라를 설치하는 최적의 해다.

[연산 횟수] : 10,000 * (10,000 - 지워진 route 개수) => 최대 1억
반례가 안떠오른다.. 그림을 그려봐도 직관적으로 맞는것 같다.

❌ 틀렸다. [1, 12][2,6] [6, 11] 에서 [1, 12] 를 먼저 들러 12에 카메라를 설치하면
[2, 6], [6, 11] 은 카메라에 걸리지 않는다.

✅ 가설3

'도착'지점 기준 오름차순으로 route 를 정렬하고 매번 가장 작은 route 의 도착지점을 지우는 것이 최적의 해다.

🔑 Kotlin Code

import java.util.*

fun solution(routes: Array<IntArray>): Int {
    val sortedRoutes = routes.sortedBy { it.last() }
    val routeList = LinkedList<IntArray>()
    for (route in sortedRoutes) {
        routeList.add(route)
    }

    var answer = 0
    // loop 을 돌며
    while (routeList.isNotEmpty()) {
        val minRouteEndPoint = routeList.first.last()
        routeList.removeFirst()
        // 첫번 째 원소의 도착지 범위 내에 있는 모든 route 를 제거함.
        while (routeList.isNotEmpty()) {
            if (minRouteEndPoint < routeList.first.first()) break
            routeList.removeFirst()
        }
        // while 을 돌 때마다 카메라 설치 횟수 + 1
        answer++
    }

    return answer
}

Java Code

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

public int solution(int[][] routes) {
    Arrays.sort(routes, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[1] == o2[1]) return o1[0] - o2[1];
            return o1[1] - o2[1];
        }
    });

    var routeList = new LinkedList<int[]>(Arrays.asList(routes));

    int answer = 0;

    while (!routeList.isEmpty()) {
        var minRouteEndPoint = routeList.getFirst()[1];
        routeList.removeFirst();
        // 첫번 째 원소의 도착지 범위 내에 있는 모든 route 를 제거함.
        while (!routeList.isEmpty()) {
            if (minRouteEndPoint < routeList.getFirst()[0]) break;
            routeList.removeFirst();
        }
        // while 을 돌 때마다 카메라 설치 횟수 + 1
        answer++;
    }

    return answer;
}