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

작성일: 2024-12-18

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

접근 방식

탐욕법 문제에는 자신이 없다. 탐욕법 문제는, 내가 현재에서 어떤 선택을 했을 때, 무조건 최선의 선택이 되도록 해서 풀어야 하는 문제이다.

어떤 선택을 내리면, 그 선택이 바로 최선의 결정이라는 것이다.

탐욕법 문제는 많이 풀어보면서 감을 익히는 게 좋을 것 같아. 대충 풀고 프로그래머스의 AI 코드 피드백을 통해 접근법을 알아봤다.

진입 or 진출 지점에 카메라를 설치하는 것이 좋다고 한다. 어디에 카메라를 설치하는 지는 중요하지 않다. 최대한 많은 차량이 통행하는 구간에 카메라를 설치하는 것이 중요하다

입출력 예시는 아래와 같이 차량이 통행한다.

-20 ----- -15
             -14 ----- -5
     -18 ------- -13
                       -5 ---- -3

따라서, -18과 -15사이에 하나, -5에 하나를 설치하여, 총 두 대의 카메라로 모든 차량을 단속할 수 있다.

하지만 입출력 예시의 설명에는, -15와 -5 지점에 카메라를 설치하고 있다. 왜 일까?

-18에 설치하나, -15에 설치하나 어차피 1번과 3번의 차량을 단속하는 것에는 변함이 없다. 하지만 -15에 설치하는 것이 풀이가 쉽다. (문제에서 차량의 진입 및 진출 시점을 알려주고 있기 때문에)

따라서, 우리는 설명에 맞게 문제에 접근하여 풀면 된다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b)->a[1]-b[1]);
        int max = routes[0][1];
        int answer = 1;

        for(int[] route:routes){
            if(route[0]<=max || max>=route[1]) continue;
            answer++;
            max = route[1];

        }
        return answer;
    }

}

먼저 진출 시점을 기준으로 오름차순 정렬을 한다. (굳이 순서대로 차량을 처리 할 필요가 없기 때문에, 범위를 기준으로 카메라를 설치하기 위해서)
진출점을 정하고, answer를 1로 초기화한다. (카메라를 하나 설치)
그리고 차량의 경로를 순서대로 처리한다.
1. 만약 현재 카메라를 설치한 지점이, 차량 경로의 진입보다 크거나, 진출보다 큰 경우는 해당 카메라의 범위에 현재 차량의 존재한다는 의미이다. 따라서 추가 설치할 필요가 없다.
2. 만약, 위의 범위안에 카메라가 존재하지 않는다면 현재 카메라로 단속할 수 없다는 의미이므로 새로운 카메라 설치가 필요하다. 따라서, 카메라를 하나 더 설치하는데, 새로운 카메라의 위치는 현재 단속 대상의 차량의 진출 시점에 설치하면 된다.