🎯문제
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 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 |
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
✏️풀이
코드
import java.util.*;
class Solution {
public int solution(int[][] routes) {
int answer = 0, cam = Integer.MIN_VALUE;
// 종료시점을 기준으로 오름차순 정렬
Arrays.sort(routes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
for(int[] route : routes) {
// 현재 카메라의 지점이 route의 시작지점보다 작다면
if(cam < route[0]) {
// route의 종료지점에 카메라를 설치
cam = route[1];
answer++;
}
}
return answer;
}
}설명
정렬과 구현을 통해 해결하였다.
answer은 설치할 카메라의 개수이고 cam은 현재 카메라의 위치이다.
routes 배열 정렬을 진행한다. 이때 정렬은 routes[i][1]을 기준으로, 즉 종료지점을 기준으로 오름차순으로 정렬을 진행한다.
예를 들어,
routes 배열 = [[-20, -15], [-14, -5], [-18, -13], [-5, -3]]
이라는 값들이 저장되어 있다고 할 때 정렬을 진행하면
routes 배열 = [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]
로 정렬이 된다.
종료지점을 기준으로 오름차순 정렬을 하는 이유는 최소한의 카메라 수를 설치하기 위해선 최대한 많이 겹치는 구간을 확인해야한다. 그렇다면 가장 많이 겹치는 구간을 확인하는 방법은 가장 먼저 끝나는 종료지점과 다른 자동차들의 시작지점을 비교하여 그 사이 구간을 찾아내는 것이기 때문이다.
예를 들어, 위에 정렬된 routes 배열을 통해 확인해보면
첫번째 차량은 -15 지점에서 종료가 된다.
두번째 차량은 -18 지점부터 시작이 된다.
그렇다면 첫번째 차량과 두번째 차량은 (-18, -15) 사이 어느 지점에 카메라를 설치하면 두 차량 모두 확인할 수 있게 된다.
두번째 차량은 -13 지점에서 종료가 된다.
세번째 차량은 -14 지점에서 시작이 된다.
그렇다면 두번째 차량과 세번째 차량은 (-14, -13) 사이 어느 지점에 카메라를 설치하면 두 차량 모두 확인할 수 있게 된다.
세번째 차량은 -5 지점에서 종료가 된다.
네번째 차량은 -5 지점에서 시작이 된다.
그렇다면 세번째 차량과 네번째 차량은 -5 지점에 카메라를 설치하면 두 차량 모두 확인할 수 있게 된다.
이렇게 종료지점과 시작지점을 확인하여 그 사이 겹치는 구간이 몇개인지 확인을 하는 방식을 사용해서 설치할 카메라의 최소 개수를 구할 수 있는 것이다.
반복문에서 현재 카메라의 지점을 route의 시작지점과 비교를 한다. 이때 시작지점보다 카메라의 지점이 작다면 route의 종료지점에 카메라를 설치하고 카메라의 개수를 뜻하는 answer의 값을 증가시켜준다.
위의 반복문이 종료된 뒤에 answer를 반환하면 문제를 해결할 수 있다!
💡느낀 점
스케줄링이 생각나는 문제였다. 이 문제 또한 기존에 비슷한 유형의 문제를 풀어본 경험이 있기에 생각보다는 쉽게 해결할 수 있었다. Level을 높여서 문제를 풀다보니 이전 Level에서 풀었던 방식을 사용하게 되는 것이 신기하기도 하고 재밌기도 했다. 비슷한 유형의 문제들을 조금 더 풀어본다면 이후 코딩테스트를 보게 되었을 때 해당 유형의 문제가 나온다면 빠르게 풀 수 있을 것 같다는 자신감이 생겼다!
링크
