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

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

코딩테스트 연습 - 단속카메라

 

그리디 알고리즘, Level 3 문제이며 문제를 자세히 보면 카메라가 종료되는 시점 기준으로 각 구간별 체크를 하면 되는 유형이다.

전출 지점에 카메라를 설치하고, 다른 차량의 전입, 전출 시점을 체크하고 있다면 체크하고 넘어가는 방식으로 넘어가면 된다.

 

코드에 대한 설명은 아래와 같습니다.

 

1. routes 를 종료 시점 기준으로 정렬, 종료 시점이 같으면 시작 시점이 더 빠른 시점 기준 정렬
2. 종료 시점 기준으로 비교하면서, 카메라를 설치할 수 있는지 체크하고 있다면 answer 값 1씩 증가

코드는 아래와 같습니다.

import java.util.*;
class Solution {
    public static int solution(int[][] routes) {
        int answer = 0;

        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) return Integer.compare(o1[0],o2[0]);
                return Integer.compare(o1[1],o2[1]);
            }
        });

        boolean visit[] = new boolean[routes.length];
        for (int i = 0; i < routes.length; i++) {
            if (visit[i] == true) continue;
            int end = routes[i][1];
            boolean canInstall = false;
            for (int j = 0; j < visit.length; j++) {
                if (visit[j] == false && routes[j][0] <= end && end <= routes[j][1]) {
                    visit[j] = true;
                    canInstall = true;
                }
            }
            if (canInstall) answer++;
        }
        return answer;
    }
}