[프로그래머스, 42884] 단속카메라 (java)

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

프로그래머스

728x90

---

메모리: 58.3 MB, 시간: 9.76 ms

사용 알고리즘: 탐욕법（Greedy）

 

1. routes를 나가는 시간 기준 오름차순으로 정렬한다.
2. 가장 먼저 나가는 차량의 나가는 시간을 out에 저장하고, out에 cctv를 설치해 준다.
3. 다음 차량 배열들을 확인한다.
4. out 이전에 들어오는 차량들은 out에 설치된 cctv와 만나게 되므로 그냥 보낸다.
   (routes가 나가는 시간 오름차순으로 정렬되어 있기 때문에, 들어오는 시간만 out 이전인지 확인해 주어도 나가는 시간은 무조건 out 이후이므로 out에 설치된 cctv와 만나게 된다.)
5. 배열을 확인하다가 out 이후에 들어오는 차량을 발견하면, 해당 차의 나가는 시간에 새로 cctv를 설치해 준다.
   즉, 해당 차의 나가는 시간을 out에 다시 저장해 주고, 3번 과정부터 다시 실행

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        
        // 끝나는 순으로 정렬
        Arrays.sort(routes, (o1, o2) -> o1[1] - o2[1]);
        
        // 필요한 CCTV 개수
        int answer = 0;
        
        // 하나의 cctv 설치 이후 처음 들어온 차량의 나가는 시간
        int out = -30_001;
        for(int[] car : routes) {
            
            // out에 cctv를 설치해줄 거임
            // out보다 먼저 들어온 차량은 out에 cctv를 설치함으로써 경로에 cctv가 하나 이상 생기게 됨
            // out보다 늦게 들어온 차량은 또 다른 cctv를 설치해주어야 함
            
            // out보다 늦게 들어온 차량 발견 시,
            // out에 cctv 설치해줌
            if(out < car[0]) {
                answer++; // cctv 설치
                out = car[1]; // 새로운 cctv 설치 장소 저장
            }
        }
        
        return answer;
    }
}