Programmers - 단속 카메라 with JAVA

 

 

문제

- 차량의 이동 경로가 주어진다.

- 이 때, 최소한의 카메라를 설치하여 모든 차를 한번이라도 단속할 때 설치해야하는 카메라의 수의 최소값을 구하라.

 

예를 들어, 다음과 같은 경우가 주어진다.

차량1 : [-20, -15] -> 차량1은 -20지점에서 고속도로에 진입해 -15지점에서 고속도로를 빠져나간다.

차량2: [-14, -5]

차량3 : [-18, -13]

차량4 : [-5, -3]

이 때, -15지점과 -5지점에 카메라를 설치하면 모든 차량을 한번은 감시하면서 최소한의 카메라를 설치한 경우가 되는 것이다.

 

 

 

로직

우선, 첫번째 인덱스를 기준으로 차량 데이터를 정렬한다.

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

순서대로 1지점, 2지점, 3지점, 4지점이라고 하겠다.

 

1지점의 최소구역인 -15지점에 카메라를 설치한다고 가정한다.

그렇다면 -15보다 더 작은 곳부터 고속도로에 진입하는 차들은 모두 이 카메라를 마주치게 된다.

따라서, 더 이상의 카메라 설치 없이 2지점 차량은 감시 카메라에 잡히게 된다.

하지만 [-14, -5]인 3지점 차량은 해당 카메라로 잡을 수 없게되므로 카메라를 한대 추가한다.

 

이 후, [-5, -3]인 4지점 차량은 -5에 설치한 카메라로 잡을 수 있다.

 

 

1. 카메라 설치 지점 최대값인 30000으로 초기화

2. 데이터를 첫번째 인덱스로 정렬

3. 카메라 설치 지점 값(a)과 현재 카메라를 설치하고자 하는 위치(b) 비교

3-1. (a > b)카메라 설치지점을 더 작은 위치로 변경

3-2. (b > a)카메라 설치지점 변경 + 카메라 설치

 

 

코드

import java.util.*;
import java.lang.Math;
class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes, Comparator.comparingInt(arr -> arr[0]));
        int check = 30000;
        for(int[] now : routes){
            if(now[0] > check){
                answer += 1;
                check = now[1];
                continue;
            }
            check = Math.min(check, now[1]);
        }
        return answer;
    }
}

 

 

 

 

다른 풀이

로직

메인 아이디어 : 순차적 설치

1. 두번째 인덱스를 기준으로 정렬한다.

두번째 인덱스를 기준으로 하는 이유 : 예를 들어, [-20, -15], [-18, -17], [-16, -5] 총 3파트가 있다고 가정하자.

첫번째 인덱스를 기준으로 하는 경우 [-20, -15], [-18, -17], [-16, -5] 가 되고 -15설치 -> -17설치 -> -16 설치가 된다.

두번째 인덱스를 기준으로 하는 경우 [-18, -17], [-20, -15], [-16, -5] 가 되고 -17설치 -> -15설치가 된다. 즉, 위의 아이디어가 성립한다.

2. 확인해가며 검사가능하면 pass, 검사 불가능하면 설치

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, Comparator.comparing(arr -> arr[1]));
        int pos = 0;
        for(int i=0; i<routes.length; i++){
            if(i == 0){
                pos = routes[i][1];
                answer += 1;
                continue;
            }
            if(routes[i][0] > pos){
                pos = routes[i][1];
                answer += 1;
            }
        }
        return answer;
    }
}