[JAVA] 단속 카메라 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL3

📂 문제 설명

 

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

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

 

제한사항

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

입출력 예

routesreturn

[[-20,15], [-14,-5], [-18,-13], [-5,-3]]

2

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 최소한의 CCTV설치를 묻는 문제이다. 그 전 문제인 섬 연결하기와 유사한 문제이다.
• CCTV설치에는 공통된 영역에 최대한 설치하도록 한다.
  • 우선 진입 시작을 기준으로 제일 빠른 순으로 Arrays.sort를 이용해 정렬해 준다.
  • 그리고 최소,최대 진입구간을 배열의 첫번째로 설정해준다.
• for문을 통해서 겹치는 구간이 있는지 판별하고 있으면 공통된 부분을 갱신해 주고 그렇지 않으면 
• CCTV수를 하나 증가시켜 주면서 공통된 진입 시작과 끝을 다시 설정해준다.   
• 이런식으로 공통된 부분이 없을때만 CCTV를 늘려주게 되면 최소 설치 갯 수를 구할 수 있다. 

📂소스코드

import java.util.Arrays;
class Solution {
public int solution(int[][] routes) {
        int answer = 1;
        
         // 진입 시작이 작은거 부터 오름차순으로 정리한다. 
        Arrays.sort(routes, (o1,o2)-> {
        	return o1[0] - o2[0];
        });

        int min = routes[0][0];
        int max = routes[0][1];
        
        for(int i=1;i<routes.length;i++) {	
        	int in = routes[i][0];
        	int out = routes[i][1];
        	
        	if(min > out || max < in) { //겹치는 구간이 없다.
        		answer++;
        		min = in;
        		max = out;
        	}
        	else { //범위안에 있는 것을 의미한다 => 계속 공통된 부분을 갱신해 주어야 한다. 
        		min = min < in ? in : min;
        		max = max > out ? out : max;
        	}
        }
        return answer;
    }
}

 

📂후 기

탐욕 문제를 풀다보니까 어느정도 감이 조금씩 생겼다. 처음에는 어렵게 접근하기만 했는데 지금은 최대한 간결하게 풀려고 노력하는 중이다! 힘내자!