[문제 링크]
https://school.programmers.co.kr/learn/courses/30/lessons/42884
[난이도]
- Level 3
[알고리즘]
- 그리디
[코드]
import java.util.*;
class Solution {
public int solution(int[][] routes) {
// 차량의 진출 지점을 기준으로 오름차순 정렬
Arrays.sort(routes, Comparator.comparingInt(o -> o[1]));
int count = 1; // 첫 번째 카메라 설치
int camera = routes[0][1]; // 첫 번째 차량의 진출 지점에 카메라 설치
for (int i = 1; i < routes.length; i++) {
// 현재 차량의 진입 지점이 마지막 설치된 카메라보다 크면 새로운 카메라 필요
if (routes[i][0] > camera) {
count++; // 새로운 카메라 설치
camera = routes[i][1]; // 카메라 위치 갱신
}
}
return count;
}
}
[풀이]
이 문제를 해결하기 위해 그리디 알고리즘을 사용합니다. 핵심 아이디어는 차량의 진출 지점을 기준으로 정렬한 후, 가장 많은 차량이 겹치는 곳에 카메라를 설치하는 것입니다.
- 차량의 진출 지점을 기준으로 정렬합니다.
- 첫 번째 차량의 진출 지점에 첫 번째 카메라를 설치합니다.
- 이후 차량을 순차적으로 확인하면서:
- 현재 차량의 진입 지점이 마지막 카메라 위치보다 크면, 새로운 카메라가 필요합니다.
- 새로운 카메라는 해당 차량의 진출 지점에 설치합니다.
설치한 카메라의 개수를 반환합니다.
