[프로그래머스] 탐욕 알고리즘 - 단속카메라

	public static int solution(int[][] routes) {
        int answer = 0;
        
        // routes[0] 오름차순 정렬
        Arrays.sort(routes,new Comparator<int[]>() {
        	public int compare(int[] o1,int[] o2) {
        		return o1[0]-o2[0];
        	}
        });
        
        int point=routes[0][0];
        int pre_count=0;	// 전에 센 값
        
        while(point<=routes[routes.length-1][1]+1) {
        	int count=0;
        	for(int i=0;i<routes.length;i++) {
        		if(routes[i][0]>point) break;
        		if(point<=routes[i][1]) {
        			count++;
        		}
        	}
        	if(pre_count>count) answer++;//값이 떨어지면 정답 증가
        	pre_count=count;
        	point++;
        }
        
        return answer;
    }

처음에 접근한 방식이다.

각 시간대별로 중첩된 차량개수를 확인하고 그 수가 떨어지면 카메라를 설치한다.

이렇게 하면 최소한으로 필요한 카메라 개수를 찾을 수 있을 것이라 생각했지만,..

수만 확인하기 때문에, 그 수에 해당하는 자동차들이 이미 센 자동차인지 새로운 자동차인지 확인하지 못해

정답 결과가 틀렸고, 각 시간별로 접근하기 때문에 시간 초과에러도 났다.

 

	public static int solution(int[][] routes) {
        int answer = 0;
        
        // routes[0] 오름차순 정렬
        Arrays.sort(routes,new Comparator<int[]>() {
        	public int compare(int[] o1,int[] o2) {
        		return o1[1]-o2[1];
        	}
        });
        
        //더 간단히 쓰는 방법
        //Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        
        int camera=-30001;
        
        for(int[] route:routes) {
        	if(camera<route[0]) {
        		camera=route[1];
        		answer++;
        	}
        }
        
        return answer;
    }
	

참고 : https://mishuni.tistory.com/53

 

해결방법을 찾으려고 생각하면 생각할수록 너무 복잡하게 생각하게 돼서.. 

결국 다른 사람의 코드를 찾아보았다..

 

생각보다 너무 간단하였다.

출차시간 기준으로 오름차순 정렬한 후, 카메라를 출차 시간으로 초기화한다.

만약 다음 자동차의 출입시간이 현재 자동차의 출차시간보다 늦다면 다음 자동차 출차 시간으로 카메라를 다시 초기화한다..

 

문제가 요구한건 복잡해 보이나.. 굉장히 간단한 코드로 구현이 되어 머리를 한대 맞은 기분이었다 또륵또륵