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

문제 풀러 가기

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
  
  
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
  
  
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
  
  
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

문제 접근

위와 같이 각 차량(0 ~ 8번)의 이동경로가 1차원 상에 표현될 때, 최소 개수의 카메라를 이용해 모든 이동 경로를 커버해야 합니다.
만약 7번 차량의 진입 지점에 카메라를 설치한다면, 해당 카메라로는 그와 겹치는 7번과 2번 차량을 감시 가능하고, 7번 차량의 진출 지점에 설치한다면 1, 2, 5, 7번 차량을 감시할 수 있습니다.

카메라를 설치할 만한 지점을 고려할 때, 제한 사항에 따라 -30,000 ~ 30,000에 이르는 구간을 전부 검토해 봐야 할까요?
어떤 카메라 x가 어떤 지점 d에 설치되어 있다고 가정하겠습니다. x를 d의 오른쪽(값이 커지는 방향) 혹은 왼쪽(값이 작아지는 방향)으로 1씩 이동시켜 보더라도, x로 커버할 수 있는 차량 정보가 바뀌는 시점은 어떤 차량 c의 진입/진출 지점입니다.
x를 이동 시켰을 때,

1) 어떤 차량의 진입지점의 왼쪽 or 진출지점 오른쪽으로 이동하는 경우
=> 기존에 감시하던 차량을 더 감시하지 못하는 상태로 변화
2) 어떤 진입지점 오른쪽으로 이동 or 진출지점 왼쪽으로 이동하는 경우
=> 새로운 차량을 감시 가능

이와 같이 정리 할 수 있고, 해당 포인트들을 제외하면 감시 가능한 차량이 변하지 않으므로 고려하지 않아도 됩니다.
탐색해야 할 상태 공간이 꽤 줄어든 것 같지만 여전히 범위가 큽니다. 차량의 대수가 최대 10,000대이고 진입/진출 지점은 총 20,000까지 될 수 있으므로 완전 탐색을 하려면 최악의 경우 20,000번의 지점 중, 카메라를 1곳에 설치하는 경우부터 20,000곳에 설치하는 경우까지 전부 계산해봐야 합니다.

필요 조건 파악

완전탐색이 사실상 불가능하므로 다른 방법을 찾아야 합니다. 어떤 지점들에 카메라를 설치해야 최종적으로 최솟값을 얻을 수 있는지는 모르지만, 분명히 알 수 있는 작은 사실이라도 있는지 생각해 봐야 합니다.
해를 구성하기 위해서 반드시 지켜야 할 조건, 꼭 포함 되어야 할 값, 포함 되지 말아야 할 값 등이 있는지 검토해 봤을 때 다음과 같은 사실을 알 수 있습니다.

가장 작은 값의 진출지점을 지니는 자동차가 고속도로에서 나가는 지점 route[i][1] 이내에 카메라가 적어도 하나 설치되어 있어야 한다.

만약 설치된 카메라 중 가장 빠른 지점에 설치된 카메라가 d에 설치되어 있다고 가정했을 때, 어떤 자동차가 d보다 작은 d0에 진출한다고 하면 감시하지 못하는 차량이 존재하는 것이 되므로 최종 해답이 될 수 없습니다.
따라서, 해를 구성하는 카메라 대수 중 1대는 무조건 최소 진출지점 값을 지니는 route[i][1] 이내에 설치되어야 합니다.
그리고 이때, route[i][1]보다 작은 지점에 설치되는 것 보다, route[i][1]와 동일한 지점에 설치되는 것이, 최소한 같거나 더 많은 차량을 감시할 수 있음을 보장하므로 route[i][1]에 설치하는 것이 최적입니다.

위 그림에서, 첫 번째 카메라는 7번 차량의 진출지점에 설치되는 것이 최적이고, 이때 1, 2, 5, 7번 차량을 함께 감시할 수 있습니다.

그림으로 보면 직관적으로 7번 차량과 함께 1, 2, 5번 차량이 감시될 수 있다는 걸 알 수 있지만, 들어오는 입력의 값을 보고 판단하려면 어떤 차량의 진입지점 route[i][0]의 값이 카메라 설치 지점(= 차량 7의 진출지점)과 같거나 작은지 확인해야 합니다.(1, 2, 5의 경우 해당 조건을 만족합니다.)

첫 번째 카메라가 어디에 설치되어야 하는지는 명확해 졌습니다. 그렇다면 k번째 카메라가 어디에 설치되어야 하는지 알려면 어떻게 해야 할까요.
바로 k - 1번째 카메라가 감시하지 못하는 차량의 이동 경로 중, 가장 작은 값을 지니는 진출지점에 설치하면 됩니다.

첫 번째 카메라 설치 지점을 구할 때와 마찬가지로, 감시하지 못하는 경로 중 최단 진출 지점을 가리키는 해당 값을 넘어갈 시, 반드시 감시 못하는 차량이 발생하고, 해당 지점 이전일 시 정확히 진출지점에 설치하는 것에 비해 이득이 없기 때문입니다.

위의 예시에서 k = 2라고 가정할 때, 2번째 카메라가 설치되어야 할 지점은, 첫 번째 카메라가 감시하지 못하는 경로 중 최소 진출 지점인, 차량 8의 진출지점이 됩니다.

같은 논리로, 3번째 카메라의 설치 위치까지 확정하고 나면, 전체 차량 이동 경로를 감시할 수 있게 되고, 이때의 카메라 설치 개수가 문제에서 구하는 최솟값이 됩니다.

정리하자면, 해가 되기 위한 필요조건을 하나씩 파악하기 위해 우선 첫 번째 카메라가 설치되어야만 하는 지점을 구했고, 이를 이용해 k번째 카메라의 설치 위치까지 확정했습니다.
답을 구하는 데 필요한 핵심 정보는 현 상태에서 감시되지 않은 차량 이동 경로 중 진출지점의 최솟값이기 때문에, 들어오는 입력 routes를 진출지점을 기준으로 정렬하면 쉽게 답을 구할 수 있습니다.
정렬 기준으로 routes[i][1]을 이용하고, 해당 경로가 현 상태에서 감시되지 못했던 경로인지 판단하기 위해 route[i][0]을 확인하면 됩니다.

이 문제는 JUNGOL - 냉장고와 표현만 다른 문제라고 봐도 무방하고, 프로그래머스 - 기지국 설치와도 같은 접근법(필요 조건 파악)으로 풀 수 있습니다.
(정렬이 필요하다는 점을 제외하면 거의 같은 문제입니다.)

코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort( routes, (int[] r1, int[] r2) -> r1[1] - r2[1] );
        int upperBound = Integer.MIN_VALUE;
        
        for(int[] route : routes){
            if(upperBound < route[0]){
                answer++;
                upperBound = route[1];
            }
        }
        return answer;
    }
}