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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42884

문제 설명

주어진 차량의 이동 경로(routes)가 있을 때, 모든 차량이 적어도 한 번은 카메라에 찍히도록 설치해야 하는 최소 카메라 개수를 구하는 문제입니다.

입력으로 주어지는 차량 이동 경로는 하나의 배열로, 한 차량은 [진입 시점, 진출 시점]의 형태로 경로를 나타냅니다.

routes = [[-20, -15], [-14, -5], [-18, -13], [-5, -3]]

=> 차가 경로를 지나가면서 모든 차량을 최소로 관찰할 수 있는 카메라 설치 위치를 찾아야 합니다. 그러기 위해선 차량 경로들이 겹치는 구간을 따져보면서 카메라를 설치해야 합니다.

핵심 아이디어

차량 경로를 진입 시점(start), 진입 시점이 같은 경우는 진출 시점(end) 기준으로 정렬하고, 각 차량의 경로를 하나씩 확인하면서 "새로운 카메라가 필요한 시점"을 판단합니다.
첫 차량의 진출 시점을 카메라 추가의 기준점(prev)으로 잡고 다른 차량들을 확인하며 기준점을 갱신합니다.

• 경로가 기존 카메라로 커버되지 않으면 새로운 카메라를 추가하고 기준점을 현재 진출 시점으로 갱신합니다.
• 겹칠 경우, 기준점을 가장 짧게 업데이트합니다.

해결 과정

1. 차량 경로 정렬
   차량 경로들을 정렬합니다. 정렬 후 경로는 다음과 같이 됩니다:

   [-20, -15], [-18, -13], [-14, -5], [-5, -3]

2. 카메라 설치 및 경로 순회
   첫 번째 차량에 카메라를 설치하고 진출 시점을 카메라 추가의 기준점으로 설정합니다.

   answer = 1, prev = -15

   이후 다른 경로를 탐색하며 현재 차량의 진입 시점 (start)이 기준점 (prev)보다 클 경우, 경로가 겹치지 않기 때문에 카메라를 추가하고 기준점을 현재 차량의 진출 시점으로 갱신합니다.
   현재 차량의 진입 시점 (start)이 기준점 (prev)보다 작거나 같다면, 경로가 겹치기 때문에 카메라를 추가하지 않고 기준점만 가장 짧게 업데이트합니다.

   cur: [-18, -13], prev: -15
   -18 < -15 -> 경로 겹침
   카메라 추가 x, 기준점만 짧게 업데이트
   prev = Math.min(-15, -13)
   prev: -15
   
   cur: [-14, -5], prev: -15
   -14 > -15 -> 경로 안 겹침
   카메라 추가, 기준점 갱신
   prev: -5

구현

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Node {
    int start;
    int end;

    public Node(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Solution {
    public int solution(int[][] routes) {
        List<Node> list = new ArrayList<>();
        for (int[] route : routes) {
            list.add(new Node(route[0], route[1]));
        }

		// 정렬
        Collections.sort(list, (o1, o2) -> {
            if (o1.start == o2.start) {
                return o1.end - o2.end;
            }
            return o1.start - o2.start;
        });

        int answer = 1;

		// 카메라 추가의 기준점
        int prev = list.get(0).end; 
        
        for (int i = 1; i < list.size(); i++) {
            Node cur = list.get(i);

			// 경로가 기존 카메라로 커버되는 경우, 기준점을 가장 짧게 업데이트
            if (cur.start <= prev) {
                prev = Math.min(prev, cur.end);
                continue;
            }

			// 커버되지 않으면, 새로운 카메라를 추가하고 기준점을 현재 진출 시점으로 갱신
            answer++;
            prev = cur.end;
        }

        return answer;
    }
}

시간 복잡도

시간 복잡도는 O(N log N)으로, 정렬 시간과 경로 탐색만 계산됩니다.