질문 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42884
프로그램 제작자
'추천 관련글,
코드 중심 개발자를 고용하십시오. 스택 기반 위치 일치. 프로그래머를 위한 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
프로그래머.co.kr
코딩테스트 전투>탐욕>과속카메라
문제 설명
고속도로를 운행하는 모든 차량이 고속도로를 이용하면서 단 한 번쯤은 단속 카메라를 만날 수 있도록 카메라를 설치할 계획입니다.
고속도로를 주행하는 차량의 경로를 인수로 하여 모든 차량이 법 집행 카메라를 한 번 이상 마주치도록 설치해야 하는 최소 카메라 수를 반환하는 솔루션 함수가 완성됩니다.
한계
- 차량 수는 1대 이상 10,000대 미만입니다.
- route는 차량의 이동 경로를 포함하고, route(i)(0)은 자동차 i가 고속도로에 진입하는 지점을 포함하고, route(i)(1)은 자동차 i가 고속도로를 떠나는 지점을 포함합니다.
- 차량 출입구에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주합니다.
- 차량은 -30,000에서 30,000 사이의 입구 및 출구 지점이 있습니다.
입력 및 출력 예
| 노선 | 반품 |
| ((-20,-15), (-14,-5), (-18,-13), (-5,-3)) | 2 |
I/O 예시 설명
카메라를 -5에 맞추면 두 번째와 네 번째 차가 카메라와 마주치게 됩니다.
-15에 카메라를 놓으면 첫 번째와 세 번째 자동차가 카메라를 만납니다.
내 코드
import java.util.*;
class Solution {
public int solution(int()() routes) {
int answer = 0;
Arrays.sort(routes, (o1, o2) -> o1(1) - o2(1));
// Arrays.sort(routes, new Comparator<int()>() {
// @Override
// public int compare(int() o1, int() o2) {
// return o1(1) - o2(1);
// }
// });
int camPos = Integer.MIN_VALUE;
for(int i=0; i<routes.length; i++) {
if(camPos < routes(i)(0)) {
camPos = routes(i)(1);
answer++;
}
}
return answer;
}
}
설명하다
- 경로가 끝나는 지점인 경로 (i)(1)에 따라 주어진 차량의 경로를 오름차순으로 정렬합니다.
- 경로는 끝점을 기준으로 오름차순으로 배열되어 있기 때문에 가장 적은 수의 카메라가 설치되도록 첫 번째 자동차의 경로 끝점에 카메라를 설치합니다.
- 카메라가 설치된 지점이 다음 차량 경로의 시작점 및 설치 위치보다 크면 이 차량의 경로에도 카메라가 포함되어 있기 때문에 카메라를 설치할 필요가 없으며 경로가 통과하는 지점도 포함됩니다.
스루 스타트는 설치 위치보다 크며, 카메라는 포함되어 있지 않으므로 카메라는 차량의 경로 끝에서 다음 차량과 비교합니다. - 이러한 방식으로 설치를 반복하면 모든 차량 경로에 설치된 카메라의 수가 최소화됩니다.