[Lv3] 단속카메라

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 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 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

 

---

 

모든 차량이 한번씩 단속카메라를 만나려면,

 

각 운전구간을 어느 기점으로 묶어줘야 하고, 그 묶은 갯수를 묻는건데,

 

이 기점은 어느 한 끝이어야 최소의 계산이 나올테고, 여기서는 나가는 기점으로 해봅니다.

 

 

우선 모든 차량의 운전방향을 통일할 겁니다.

for(int i=0;i<routes.length;i++) {
    Arrays.sort(routes[i]);
}

혹시 역주행 하는 경로가 있었더라도 상관없이 구간 자체로만 계산할 수 있게요.

 

 

우리는 좌→우로 움직이면서 들어올 애들을 큐에 넣으면서 탐색할겁니다. 배열은 들어오는 시점 순으로 정렬합니다.

Comparator<int[]> c1 = (a,b)->{
    return a[0]-b[0];
};
Arrays.sort(routes, c1);

 

 

그리고 카메라를 설치할 시점을 나가는 기점으로 합니다.

 

즉, 큐에 들어있는(현재 시점에 들어올 애들이 다 뭉쳐있는 그룹) 애들 중 가장 빨리 나가는 애를 기준으로 할 겁니다.

Comparator<int[]> c2 = (a,b)->{
    return a[1]-b[1];
};
PriorityQueue<int[]> queue = new PriorityQueue<>(c2);

 

①　　────

②　　　　─────

③────────

④　　　　　　　───…

을 봅시다.

 

먼저 ③이 그룹에 들어옵니다.

현재 기준으로 가장 빨리 나갈 애는 ③입니다. ③이 나갈 시점보다 다음 애(들어오는 정렬이니 ①)가 들어오긴 하는가? 들어오니까 ①도 넣습니다.

 

현재 기준으로 가장 빨리 나갈 애는 ①로 바뀌었네요. ①이 나갈 시점보다 다음 애(들어오는 정렬이니 ②)가 들어오긴 하는가? 들어오니까 ②도 넣습니다.

 

현재 기준으로 가장 빨리 나갈 애는 여전히 ①이군요. ①이 나갈 시점보다 다음 애(들어오는 정렬이니 ④)가 들어오긴 하는가? 안들어오네요. 여기까지 그룹을 묶습니다.

 

①　　────|

②　　　　──|───

③──────|──

④　　　　　　|　───…

①가 나갈 시점을 세로로 선을 그어보면 ①,②,③ 모두 선을 지나갑니다. 이게 하나의 그룹이 되고 하나의 감시카메라만 설치해도 됩니다.

 

 

즉, 우리는 큐가 비어있을 때 다음 index의 애를 하나 무조건 넣고,

 

큐가 비기 전까지 큐에서 가장 빨리 나갈 애를 앞세워서, 그 애가 나갈 시점보다 다음 번 애가 들어오는게 빠르면 큐에 동참(큐에 넣고, index도 다음칸으로).

('가'의 오른쪽 끝보다 '나'의 왼쪽 끝이 먼저라는 건 '가'와 '나'의 막대기가 겹치는 구간이 있다는 소리)

 

큐에 동참할 애가 다 모였으면 모두 함께 지우면서 answer++.

 

 

루프 돌텐데 당연히 큐가 비어있고 다음 index의 애를 하나 무조건 넣는걸로 그룹을 시작..

 

 

이렇게 그룹 수가 감시카메라가 함께 감독할 덩어리 수.

int index = 0;
int answer = 0;
while(index<routes.length) {
    queue.add(routes[index]);
    index++;
    while(index<routes.length) {
        int[] prior = queue.peek();
        if(routes[index][0]<=prior[1]) {
            queue.add(routes[index]);
            index++;
        } else break;
    }
    while(!queue.isEmpty()) {
        queue.poll();
    }
    answer++;
}
return answer;