[프로그래머스] 단속카메라 -Java

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

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

import java.util.Arrays;
class Solution {
	    public int solution(int[][] routes) {
	        int answer = 0;
	        Arrays.sort(routes, (o1,o2)->(o1[0]-o2[0]));
	        
	        int start=routes[0][0],end=routes[0][1];
	        for(int i=1; i<routes.length; i++) {
	        	if(routes[i][0]<=end) start=routes[i][0];
	        	else {
	        		answer++;
	        		 start=routes[i][0];
	        		 end=routes[i][1];
	        	}
	        	
	        	if(end>=routes[i][1]) end=routes[i][1];
	        }
	        return answer+1;
	    }
	}

소요시간 : 45분

 

전형적인 그리디 문제입니다! 

 

로직을 살펴보면

일단 정렬을 해줍니다.

진입   진출

-20     15

-18    -13

-14    -5

-5      -3

 

그리고 각 차량의 공통적인 범위를 찾아줍니다. 만약 공통범위를 벗어난다면 카메라의 수를 +1 해주고 범위를 바꿔줍니다.

 

우선 단속카메라의 범위는 -20~15입니다.

2번째 routes의 범위는 -18~-13입니다. -> 단속카메라의 범위는 -18~-13입니다.

3번째 routes의 범위는 -14~-5입니다.   -> 단속카메라의 범위는 -14~-13 입니다. 

4번째 routes의 범위는 -5~-3입니다.    ->단속카메라의 범위인  -14 ~ -13 과 공통부분이 없습니다. 

그렇다면 카메라의 개수를 1 증가시켜주고 다시 단속카메라의 범위를 -5 ~ -3 으로 바꿔줍니다.

 

이렇게 하면 총 필요한 카메라개수 -1 개가 나옵니다. 마지막으로 answer+1을 리턴해주면 됩니다.