[프로그래머스 자바] 단속카메라 (Lv.3)

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

프로그래머스

 

 

import java.util.*;

class Solution {
    
    int cameraCount = 0;
    int lastEndTime = Integer.MIN_VALUE;
    List<Car> cars = new ArrayList<>();
    
    public int solution(int[][] routes) {
        
        for (int[] route : routes) {
            cars.add(new Car(route[0], route[1]));
        }
        
        Collections.sort(cars);
        
        for (Car car : cars) {
            if (lastEndTime < car.startTime) {
                lastEndTime = car.endTime;
                cameraCount++;
            }
        }
        
        return cameraCount;
    }
    
    class Car implements Comparable<Car> {
        
        int startTime, endTime;
        
        public Car(int startTime, int endTime) {
            this.startTime = startTime; 
            this.endTime = endTime;
        }
        
        @Override
        public int compareTo(Car o) {
            return Integer.compare(this.endTime, o.endTime);
        }
    }
}

 

 

조건은 모든 차량이 최소 1번은 단속 카메라를 만나야 한다. 

 

개인적인 취향으로 route[0], route[1] 이런 식으로 의미를 알 수 없는 값을 싫어해서 따로 객체 Car를 만들어서 진입, 진출 시점으로 묶어주었다. 그리고 객체 간 정렬일 때는 Comparable 인터페이스로 구현해서, Collections.sort 에 따로 Comparator를 만들어 주지 않는 취향도 있어서 이를 compareTo 메서드를 구현해 주었다. 

 

모든 차량에 대해서 진출 시점을 오름차순으로 해두고, 단속 카메라를 항상 각 차량에 대해서 진출 시점에만 배치를 한다고 생각하면, 최소 1번만 단속 카메라만 만나면 되므로 마지막으로 단속된 차량의 진출 시점까지는 추가적인 단속 카메라가 필요하지 않게 된다. 

 

따라서 마지막 진출 시점(lastEndTime) 이후에 현재 차량이 진입했다면, 단속 카메라를 하나 더 추가한 뒤 마지막 진출 시점을 현재 차량의 진출시점으로 갱신해준다. 

 

이후 모든 차량에 대해서 계산하고 나서 단속 카메라 개수를 리턴하면 끝.