문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42884
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
차들이 공통적으로 사용할 수 있는 카메라의 수를 그리디적으로 찾아야 한다.
class Solution {
public int solution(int[][] routes) {
int answer = 1;
ArrayList<Route> routeList = new ArrayList<Route>();
for (int i = 0; i < routes.length; i++) {
Route currRoute = new Route(routes[i][0], routes[i][1]);
routeList.add(currRoute);
}
Collections.sort(routeList);
Route tmp = routeList.get(0);
for (int i = 1; i < routeList.size(); i++) {
Route curr = routeList.get(i);
if (tmp.exit > curr.exit) {
tmp = curr;
}
else if (tmp.exit < curr.enter) {
answer++;
tmp = curr;
}
}
return answer;
}
class Route implements Comparable<Route>{
int exit;
int enter;
public Route (int enter, int exit) {
this.enter = enter;
this.exit = exit;
}
@Override
public int compareTo(Route r) {
if (this.enter > r.enter) return 1;
else if (r.enter == this.enter) return 0;
else return -1;
}
}
}