문제

Programmers - 단속카메라

요약

모든 차를 단속할 수 있도록 설치하는 카메라의 최소 개수를 구하라

접근

처음에 문제를 봤을 때, 차량마다 출발 지점을 기준으로 정렬을 하고 각 차량마다 겹치는 구간에 카메라를 두면 되겠다고 생각했다.

그러고 문제의 TC를 이 논리로 푸니까 개수가 안맞았다.

20분 동안 어떻게 풀지 고민했는데 답이 안나와서 스터디를 같이 하는 친구가 푼 코드에 주석을 읽고 어느정도 접근 방식을 알고 접근했다.

그 접근 방식은 아래와 같다.

1. 정렬을 한다.
2. 자동차의 고속도로 나간 지점에 카메라를 세운다.
3. 새로 세운 카메라를 다음 차량이 잡을 수 있는지를 검사하며 새로운 카메라를 설치할지말지 결정한다.

알고리즘

1. 차량별 고속도로를 나간 시점을 기준으로 정렬한다.
2. 최초 카메라 설치를 첫번째 차량이 나간 시점으로 초기화한다.
3. 차량 전체를 순회하며 최근 설치된 카메라로 해당 차량을 탐지할 수 있는지 판단
   3-1. 탐지할 수 없다면, 해당 차량의 탈출이 나가는 시점으로 최근 카메라 설치 위치를 이동
   3-2. 카메라 개수 증가

제출 코드

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int[] cameras = new int[routes.length];
        
        // 고속도로 탈출한 시점으로 정렬
        Arrays.sort(routes, (a, b) -> a[1] - b[1]);
        
        // 최근에 설치한 카메라 위치
        int newCam = routes[0][1]; // 기본 값으로 첫번째 차량의 고속도로 나간 지점을 잡음
        answer++; // 카메라 개수 1 증가
        
        for (int i = 1; i < routes.length; i++) {
            // 설치한 카메라가 다음 자동차의 출발지를 못잡는다면, 새로운 카메라 설치
            if (routes[i][0] > newCam) {
                newCam = routes[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}

깨달은 점

Greedy라는걸 파악하기도 어렵고, 문제를 접근하는 아이디어조차 떠올리기 힘들었다.
Greedy는 미래를 생각안하고, 그 순간순간 가장 좋아보이는 최적의 선택을 하는 알고리즘 설계 기법... 이걸 어떻게 아냐...
많이 접해봐야 이게 그리디 문제인지 알 것 같다.