Programmers 단속카메라 java 풀이

 

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

나의 풀이

 주어진 배열에서 입장하는 위치에 따라 배열을 정리하고, 하나씩 값을 꺼내면서 출구 위치 최소값을 저장했다. 저장된 최소 값보다 입장 위치가 더 크다면 겹치는 구간이 없다는 말이므로 카메라 갯수를 1씩 증가시킨다. 접근은 이렇게 하였는데, 구현을 나누어서 해보았다. 먼저는 배열 자체를 정렬해서 구현한게 코드1, 두 번째로는 객체를 생성하고 객체 배열을 만들어서 정렬하는 방식. 사실 어떻게 풀던 동일하고 실행시간도 크게 차이는 안났지만 비교값해야할 변수가 더 다양해질 경우와 객체를 이용하는 방식으로도 풀어보고 싶어서 괜한? 코드를 더 작성해봤다.

 

 

코드1

import java.util.*;
class Solution {
     public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, new Comparator<int[]>() {
            public int compare(int[] r1, int[] r2) {
                return r1[0] - r2[0];
            }
        });
         
         int max = Integer.MIN_VALUE;
         
         for(int i=0; i<routes.length; i++) {
             if(max >= routes[i][0]) {
                 if(max> routes[i][1])
                     max = routes[i][1];
                 continue;
             }
             max = routes[i][1];
             answer++;
         }
        
        return answer;
    }
    
    
}

 

코드2

import java.util.*;
class Solution {
    class Route implements Comparable<Route> {
        int in;
        int out;
        
        Route(int in, int out) {
            this.in = in;
            this.out = out;
        }
        
        @Override
        public int compareTo(Route r2) {
            if(this.in<r2.in) return -1;
            else if(this.in > r2.in) return 1;
            else {
                if((this.out-this.in) < (r2.out-r2.in)) return -1;
                else if((this.out-this.in) > (r2.out-r2.in)) return 1;
                else
                    return 0;
            }
        }
    }
    
    public int solution(int[][] routes) {
        int answer = 0;
        Route[] arr = new Route[routes.length];
        for(int i=0; i<routes.length; i++) {
            arr[i]  = new Route(routes[i][0], routes[i][1]);
        }
        
        Arrays.sort(arr);
        
        int min = arr[0].in;
        int max = arr[0].out;
        answer++;
        for(int i=1; i<arr.length; i++) {
            Route route = arr[i];
            if(route.in > max ) {
                answer++;
                min = route.in;
                max = route.out;
            } else {
                min = route.in;
                if(route.out<max) max = route.out; 
            }
        }
        
        return answer;
    }
    
    
}