문제 링크 : Programmers
나의 풀이 : Git Solution
문제내용
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때,
모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점,
routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. - 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예 설명
- 5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
- 15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
routes | return |
---|---|
[[-20,15], [-14,-5], [-18,-13], [-5,-3]] | 4 |
풀이과정
초기구상
- 고속도로에서 진출이 빠른 차량을 찾아서 그 위치에 카메라를 설치하자
- 그러면 진출이 가장 빠른 차량의 위치에 카메라를 설치했기 때문에 그 지점 이전에 출발하는 차량은 모두 단속이 가능하다.
- 단속된 차량을 제외한 목록에서 가장 진출이 빠른 차를 찾고 위와 같은 프로세스를 반복하면 해결
진행하며 수정된 내용
- 우선 진출이 빠른 순으로 정렬해서 진행하면 빨리 결과를 볼 수 있을듯
최종형태
- 진출순 정렬
- 진출이 가장 빠른 자리에 카메라 설치
- 카메라 설치 지점보다 진입한 차량을 만나면 카메라 설치를 해당 차량의 진출지점으로 설정
- 카운트 증가
- 반복
public static int process2(int[][] routes){
int cnt = 0;
int cam = Integer.MIN_VALUE;
for(int i=0; i< routes.length; i++) {
if(cam < routes[i][0]){
cam = routes[i][1];
cnt++;
}
}
return cnt;
}
실행결과
- 정확성 테스트
테스트 1 〉 통과 (0.60ms, 52.5MB)
테스트 2 〉 통과 (0.68ms, 52.4MB)
테스트 3 〉 통과 (0.68ms, 52.9MB)
테스트 4 〉 통과 (0.90ms, 52.5MB)
테스트 5 〉 통과 (0.80ms, 53.2MB)
- 효율성 테스트
테스트 1 〉 통과 (4.05ms, 52.9MB)
테스트 2 〉 통과 (2.95ms, 56.2MB)
테스트 3 〉 통과 (8.42ms, 55.8MB)
테스트 4 〉 통과 (1.06ms, 51.7MB)
테스트 5 〉 통과 (13.72ms, 56.4MB)
'알고리즘' 카테고리의 다른 글
[HackerRank] The Bomberman Game - 2021.08.11 (0) | 2021.09.15 |
---|---|
[Programmers] 섬 연결하기 - 탐욕법 - 2021.08.02 (0) | 2021.09.15 |
[Programmers] 기둥과 보 설치 - 2020 KAKAO BLIND RECRUITMENT - 2021.07.26 (0) | 2021.09.15 |
[Programmers] 자물쇠와 열쇠 - 2020 KAKAO BLIND RECRUITMENT - 2021.07.19 (0) | 2021.09.15 |
[Programmers] 조이스틱 - 탐욕법 - 2021.07.16 (0) | 2021.09.15 |