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

난이도 : Level 3

유형 : 그리디

구현 시간 : 20분

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

프로그래머스

 

 

풀이 힌트

1. 차량 구간을 정렬해보자.
   • 시작점 기준일까? 종료점 기준일까?
2. 카메라 설치 위치를 정하면 그 이후 구간을 어떻게 커버할 수 있을까?
   • 겹치는 구간이 있으면 한 카메라로 여러 차량을 커버할 수 있겠지?
3. 그리디 선택 가능성
   • “현재 구간을 가장 효율적으로 커버할 수 있는 위치”에 카메라를 설치하면 이후 구간에도 최적 선택으로 이어질까?"

생각해보기

힌트를 보면 겹치는 구간을 최대한 활용하는 방식이 핵심입니다.

• 만약 구간이 겹치면 같은 카메라 하나로 여러 차량을 찍을 수 있음.
• 가장 먼저 끝나는 구간에 카메라를 설치하면, 남은 차량 구간 중에서 가장 많은 구간을 한 번에 커버할 수 있습니다.
• 겹치지 않는 구간이 나오면 새 카메라를 설치하고, 다시 겹치는 범위를 계산하면 됩니다.

즉, 그리디 알고리즘 + 정렬 조합이 효율적이라는 것을 유추할 수 있습니다.

 

최종 풀이

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        // 1. 차량 구간 종료점 기준 정렬
        Arrays.sort(routes, (a, b) -> a[1] - b[1]);

        int count = 0;            // 설치한 카메라 수
        int camera = Integer.MIN_VALUE; // 현재 설치된 카메라 위치

        for (int[] route : routes) {
            // 현재 카메라가 차량 진입지점보다 왼쪽이면 새 카메라 설치
            if (camera < route[0]) {
                camera = route[1]; // 구간 종료점에 카메라 설치
                count++;
            }
        }

        return count;
    }
}

 

트러블슈팅: 배열에서 카메라 변수로

처음에는 차량 구간의 **겹치는 범위(overlap 배열)**를 계속 기록하며, 새 구간과 겹치는지 판단하는 방식으로 접근했습니다.

int[] overlap = routes[0].clone();
int count = 1;

for(int i = 1; i < routes.length; i++) {
    int[] route = routes[i];
    
    if(overlap[1] < route[0]) { // 겹치지 않음
        count++;
        overlap = route.clone();
    } else {
        overlap = new int[]{route[0], Math.min(overlap[1], route[1])};
    }
}

• 장점: 직관적으로 “겹치는 구간을 좁혀서 카메라 설치 위치를 결정”하는 방법
• 단점: 배열 복사(clone)와 최소값 계산(Math.min)이 반복되며, 코드가 조금 번잡함

개선 아이디어

종료점 기준으로 정렬했을 때 가장 오른쪽 위치(종료점)에 카메라를 설치하는 것이 최적을 보장한다는 것을 증명식을 통해 이해했습니다.

증명식 요약

• 그리디 선택 속성: 현재 구간 종료점에 설치하면 이후 최대 구간 커버 가능
• 최적 부분 구조: 남은 구간에도 동일 전략 적용 가능
• 교환 논증: 다른 최적해의 첫 카메라를 그리디 위치로 바꿔도 카메라 수 증가 없음

→ 따라서, overlap 배열을 쓰는 방식과 결과는 같지만, 변수 하나로 관리하는 방식이 더 효율적임을 수학적으로 증명 가능.