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

문제

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

프로그래머스

 

---

 

문제 개요

고속도로를 이동하는 차량들의 경로가 주어질 때, 모든 차량이 단속 카메라를 한 번 이상 만나도록 카메라를 설치하려 한다. 차량의 진입 지점과 진출 지점을 기준으로 최소한의 카메라를 설치하는 문제이다.

접근 방법

1. 차량의 진출 지점을 기준으로 오름차순 정렬:
   모든 차량이 카메라를 만나기 위해 가장 빨리 고속도로를 떠나는 차량의 진출 지점에 카메라를 설치한다는 전략을 세운다. 이를 위해 Arrays.sort를 사용하여 routes 배열을 진출 지점(o1[1]) 기준으로 정렬한다.
2. 카메라 설치와 경로 확인:
   • 첫 번째 차량의 진출 지점에 카메라를 설치한다.
   • 이후 차량들을 순회하며, 해당 차량의 진입 지점이 현재 설치된 카메라의 범위를 벗어나는지 확인한다.
   • 만약 범위를 벗어난다면 새로운 카메라를 설치하고, 그 차량의 진출 지점을 기준으로 카메라 위치를 갱신한다.
3. 최종 카메라 수 계산:
   • 초기 설치한 카메라를 포함하기 위해 결과 값에 1을 더한다.

 

코드

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