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

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

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

문제 설명 :

고속도로를 이동하는 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지 구하기

 

문제 풀이 : 

routes 배열에서 진출 지점을 기준으로 오름차순 정렬을 합니다.

배열의 처음 원소의 진출 지점을 temp 변수에 넣고 다음 차량의 진입 지점을 비교하면서 

만약, 진출 지점보다 진입 지점이 더 큰 숫자라면 카메라를 추가 하고 temp에 진출 지점을 갱신해줍니다.

 

예를 들어 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 라면

정렬하면 [-18, -13], [-14, -5], [-5, -3], [-20, 15]가 됩니다.

최소 한 번으로 answer = 1

 

첫 번째 원소 진출 지점인 -13을 temp에 넣는다.

temp 와 진입 지점 -14 비교, 넘어감

temp 와 진입 지점 -5 비교, 카메라(answer) 추가, temp에 진출 지점 -3 추가

temp 와 진입 지점 -20 비교, 넘어감

import java.util.Arrays;

class Solution {
    public static int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes,(o1,o2)->Integer.compare(o1[1], o2[1]));
        int temp = routes[0][1];
        
        for (int i = 1; i < routes.length; i++) {
        	if(routes[i][0] > temp) {
        		answer++;
        		temp = routes[i][1];
        	}
        }
        return answer;
    }
}