[프로그래머스] LV3 단속카메라(JAVA)

문제

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

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

문제풀이

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b) -> a[1] - b[1]);
        int out = routes[0][1];
        int answer = 1;
        
        for(int i = 1; i < routes.length; i++) {
            //진입지점이 진출지점보다 크다면 +
            if(routes[i][0] > out) {
                out  = routes[i][1];
                answer++;
            } 
        }
        return answer;
    }
}

 

핵심아이디어

1. 진출지점을 오름차순으로 정렬

2. 진입지점이 진출보다 크면 감시카메라 대수를 늘려주고 진출지점 업데이트