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

단속카메라

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes	return
[[-20,15], [-14,-5], [-18,-13], [-5,-3]]	2

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

 

 

풀이

 

메모장에 숫자를 그려놓고 규칙을 생각해보았습니다.

들어오는 시점을 오름차순으로 정렬했을 때 , 문제의 예시에서는

 

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

 

이렇게 나오게 됩니다

 

들어오는 시점을 x 나가는 시점을 y라고하면

 

x1 > y 일 경우 카메라를 새로 설치해줘야 되는것을 알 수 있었습니다.

 

규칙만 생각하면 풀기 쉬운 문제였습니다.

또한 카메라의 시점을 작은것으로 바꿔주는 과정도 필요합니다.

import java.util.*;
class Solution {
    public static int solution(int[][] routes) {
        int answer = 0;
        ArrayList<Node>car = new ArrayList<>();
        ArrayList<Integer>list = new ArrayList<>();
        for(int i=0; i<routes.length; i++) {
            car.add(new Node(routes[i][0],routes[i][1]));
        }
        Collections.sort(car);
        
            answer++;
        int camera_range = car.get(0).end;
        for(int i=1; i<car.size(); i++) {
            Node a = car.get(i);
            
            if(a.start>camera_range) {
                answer++;
                camera_range = a.end;
            }
            else {
                camera_range = Math.min(camera_range, a.end);
            }
        }
        
        
        return answer;
​
    }
}
class Node implements Comparable<Node>{
    int start,end;
    Node(int start, int end){
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Node o) {
        if(this.start==o.start) {
            return o.end-this.end;
        }
        return this.start-o.start;
    }
}