프로그래머스 단속카메라

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

코딩테스트 연습 - 단속카메라

 

풀이 : 탐욕 알고리즘

① 구간 시작위치가 가장 먼저인 구간부터 차례로 비교하면서 카메라의 설치 구간을 탐색

② 카메라가 설치된 구간과 route(자동차 통과구간)를 비교하면서 카메라 설치 구간을 줄여나감.

③ 겹치는 구간이 없으면 자동차 통과구간을 카메라 설치구간에 추가함.

 

 

구현 JAVA

import java.util.*;

public int solution(int[][] routes) {
	
	//먼저 빠져나가는 거리 순으로 정렬
	Arrays.sort(routes, (o1, o2) -> o1[0] - o2[0] );	
	
	List<int[]> cameraList = new ArrayList<>();
	
	for( int[] route : routes ) {
		
		//기존 카메라가 설치된 구간을 통과하는지 담을 변수
		boolean isMeet = false;
		
		for(int[] camera : cameraList) {
		//카메라가 설치된 구간과 route(자동차 통과구간)를 비교하면서 
		//카메라 설치 구간을 줄여나감.
			
            // 두 구간이 겹치는 부분이 있으면
			if(camera[1] >= route[0] && camera[0] <= route[1]) {
				// 카메라 구간의 시작위치보다 자동차 통과구간의 시작위치가 나중이면
				if(camera[0] <= route[0] ) {
					// 카메라 구간의 사직위치를 자동차 통과구간의 시작위치로 변경
					camera[0] = route[0];
				}
				// 카메라 구간의 종료위치가 자동차 통과구간의 종료위치가 먼저면
				if(camera[1] >= route[1]) {
					// 카메라 구간의 종료위치를 자동차 통과구간의 종료위치로 변경
					camera[1] = route[1];
				}
				isMeet = true;
			}	
		}
		//겹치는 구간이 없으면 자동차 통과구간을 카메라 설치구간에 추가함.
		if(!isMeet) {
			cameraList.add(route);
		}
	}
	return cameraList.size();
}