며칠전에 풀어놓고 포스팅이 귀찮아서 미루다가.. 이제야 포스팅을 해봄니다.. ^^..
프로그래머스 고득점 kit 그리디 분류의 Level3문제를 풀었다. 이걸로 그리디 분류의 문제도 끝 ✅ !!
(문제 링크)
문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예
| routes | return |
|---|---|
| [[-20,15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
풀이 방법
이 문제는 하나의 단속카메라로 단속할 수 있는 차량의 그룹의 개수를 찾아내야 하는 문제이다. 들어온 차량 순서대로 경로를 관찰하여 가장 먼저 나가는 차량의 나가는 위치에 단속카메라를 설치한다면 그 이전까지 들어온 모든 차량은 그 단속카메라로 단속이 가능한 것이다.
이를 코드로 구현할 수 있도록 구성해보았다.
먼저 진입한 지점을 기준으로 정렬을 해준다. 차량을 순차적으로 탐색하면서 현재 차량의 진입 지점이 단속카메라 이전이라면, 현재의 단속카메라 위치로 단속할 수 있으므로 탐색을 계속 진행한다. 이 때, 탐색을 진행하며 나가는 위치가 더 작은 것으로 단속카메라 위치를 계속해서 갱신해준다.
만약 진입 지점이 단속카메라보다 크다면 ( 같다면 단속이 가능하다 ) 같은 카메라로 단속할 수 있는 그룹이 아니므로 이전까지 탐색한 차량들이 한 그룹이 되는 것이다. 그러므로 카메라의 개수를 증가시켜 주고, 현재의 나가는 지점을 단속카메라 위치로 지정해주고 위의 과정을 반복한다.
문제의 입출력 예 설명에서는 -15, -5에 카메라를 설치하여 2개라는 답이 나왔다고 설명되어 있지만 ( 물론 알고리즘에 따라서 다양하게 나올 수 있음 ), 본인이 구상한 알고리즘으로 문제를 푼다면 -13과 -3에 카메라를 설치하는 결과가 나온다.
코드
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public int solution(int[][] routes) {
int answer = 1;
Arrays.sort(routes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int flag = routes[0][1];
for(int i=1; i<routes.length; i++){
if(routes[i][0] <= flag){
if(flag < routes[i][1]) continue;
}
else answer++;
flag = routes[i][1];
}
return answer;
}
}