문제
https://school.programmers.co.kr/learn/courses/30/lessons/42884
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
입력
2차원 배열 형태의 차량의 이동 경로
출력
최소 카메라 설치 수
풀이
제한조건
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
접근방법
문제를 보자마자 그리디 문제라는 생각이 들었다.
차근 차근 문제에 접근해보자.
입력예시
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]입력 예시를 좌표평면 상에 그려보자.
카메라는 최소한의 수로 설치하면 된다.
따라서 최대한 많이 겹치는 구간에 설치한다면, 최소한의 설치로 모두 단속할 수 있게 된다.
완전 탐색방법을 이용한다면 효율성에 문제가 발생할 수 있다.
1. 문제에서 주어진 가장 빠른 출발점부터, 가장 늦은 출발점까지 구한다.
2. 각 좌표에 몇 대의 차량이 지나가는지 카운팅한다.
3. 가장 많이 지나가는 지점에 카메라를 설치하고 단속된 차량을 모두 제외한다.
4. 1부터 반복한다.너무 많은 탐색과 공간이 필요하다.
따라서 조금 그리디 하게 접근해보자.
정렬을 통해 가장 출발점이 왼쪽, 끝나는 점은 오른쪽인 순으로 정렬을 한다.
class Route implements Comparable<Route>{
int start;
int end;
Route(int a, int b){
start = a;
end = b;
}
public int compareTo(Route o){
if(this.end == o.end)
return this.start - o.start;
return this.end - o.end;
}
}그 다음 우선순위큐를 이용하여 하나씩 꺼내며
카메라의 위치와 차량의 구간을 비교하며, 카메라의 설치 필요성을 조사하여 설치한다.
(가장 출발점이 왼쪽, 끝나는 점은 오른쪽으로 정렬하였기 때문에 카메라를 가장 오른쪽 끝에 설치해야 다른 차량과 겹칠 확률이 높다!)
int answer = 0;
int camera = -30001;
while(!pq.isEmpty()){
Route cur = pq.poll();
if(camera < cur.start){ // 현재 카메라 위치에서는 해당 차량을 단속할 수 없다.
camera = cur.end; 해당 차량의 마지막 위치에 카메라 설치
answer++;
}
}코드
import java.util.*;
class Route implements Comparable<Route>{
int start;
int end;
Route(int a, int b){
start = a;
end = b;
}
public int compareTo(Route o){
if(this.end == o.end)
return this.start - o.start;
return this.end - o.end;
}
}
class Solution {
public int solution(int[][] routes) {
PriorityQueue<Route> pq = new PriorityQueue();
for(int[] data : routes){
pq.add(new Route(data[0], data[1]));
}
int answer = 0;
int camera = -30001;
while(!pq.isEmpty()){
Route cur = pq.poll();
if(camera < cur.start){
camera = cur.end;
answer++;
}
}
return answer;
}
}