단속카메라 [자바]

 

🧫 문제 분석

✔️ 출처

단속카메라 level 3

📖 문제

 

탐욕법 문제로

예전에 포스팅했던 요격시스템과 비슷한 문제다.

 

 

시작지점을 기준으로 정렬하고 

(다음 차량의 시작지점 <= 기준 차량의 끝지점) 이면 하나의 단속 카메라 범위에 들어간다. 

이때 다음 차량의 끝지점이 기준 차량의 끝지점보다 작다면 기준 차량의 끝지점을 갱신한다. 

 

왜냐하면 최소한의 카메라를 설치해야하기에 

최대한 겹치는 부분에 카메라를 놓아야한다. 

이때 끝지점이 제일 작은 것을 기준으로 그 안에 겹치는 부분이 최대 중복 차량의 위치이며

카메라 설치 위치이다.

 

잘 모르겠다면 요격시스템 포스팅을 보길 바란다. 

 

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    // 고속도로 진입 지점을 기준으로 정렬
    // 끝 범위 안에 시작지점이 있으면 하나로 취급
    
    public int solution(int[][] routes) {
        
        Arrays.sort(routes, (o1, o2) -> o1[0] - o2[0]);
        
        int end = 1000000;
        int answer = 0;
        int idx = 0;
        
        while (idx < routes.length) {
        
            // 끝지점 안에 시작지점이 포함되어 있다면 
            if (end >= routes[idx][0]) {
                end = Math.min(end, routes[idx][1]);
                idx++;
                
            }else {
                answer++;
                end = 1000000;
            }
            
        }
        
        return answer + 1;
    }
}

 

❗ 오답노트 / 필요한 지식