[프로그래머스 Lv3][자바] 단속카메라

❓문제설명

단속카메라

프로그래머스

 

---

🔍문제해석

어떤걸 풀어야 할까?

• 차량의 이동경로가 주어지면 모든 차량을 촬영할 수 있는 단속 카메라의 최소 갯수를 구하라.
• 차량의 이동경로는 이차원 배열로 주어진다. ex ) i번째 차량 경로 시작지점, 끝난시점 [-20, -15 ]
• 카메라가 시작, 끝 지점을 포함하여 -20 ~ -15 사이에 있다면 차량과 만난걸로 간주한다.

---

🧐문제풀이

• 문제 풀이 구상

감시 카메라의 최소 갯수를 구하려면 최대한 많은 차량들이 지나가는 공통 구간을 구해야한다고 생각했다.

이동경로의 공통 부분을 구하고, 그 부분을 벗어나는 경로라면 새로운 카메라를 배치하여 커버하도록 해야한다.

새로 배치한 카메라가 최대한 커버할 수 있는 경로를 구하고, 그걸 넘어서면 다시 카메라 추가 배치... 이 과정을 

차량 이동경로 배열이 끝날때 까지 반복하면 모든 차량이 카메라를 한 번씩 만나기 위해 설치해야하는 카메라의 최소 갯수를 구할 수 있다.

• 알고리즘 선택

모든 차량을 만날 수 있도록 최적의 카메라 설치 위치를 찾는 것이 문제이기 때문에

그리디 알고리즘을 이용해 풀었다.

 

 

---

！제출코드

1. 차량의 시작지점, 끝지점을 담을 클래스를 만들어준다.
2. 차량의 이동경로가 카메라의 커버 범위에 포함되는지의 비교를 쉽게 하기 위해 시작 지점이 작은 순대로 정렬될 수 있도록 compareTo 오버라이드하여 작성.
3. 차량 이동경로 배열을 각 차량별로 객체생성하고, 리스트에 담는다.
4. sort 함수를 호출해서 오름차순 정렬한다.
5. 카메라 범위를 계산할 변수 생성.
6. 차량리스트 반복문 시작.
7. 처음 차량의 시작 끝 지점을  카메라 범위로 대입, 카메라 갯수 +1
8. 다음 인덱스 부터
   1. 차량의 시작지점이 카메라의 end보다 크다면, 현재의 카메라가 커버하지못하는 것이기 때문에 범위 재정의하고, 카메라 + 1.
   2. 차량의 이동경로가 카메라 커버범위 내라면 차량의 시작과 끝지점을 카메라의 범위로 대입하면서 range를 좁혀준다.
9. 반복문이 끝난 후 Count 리턴

import java.util.*;

class Solution {

   public static int solution(int[][] routes) {
   
        List<CarRoute> list = new ArrayList<>();
        // (3)
        for( int [] r : routes ) {
            CarRoute c = new CarRoute(r[0],r[1]);
            list.add(c);
        }
        // (4)
        Collections.sort(list);
        
        int count = 0;
        // (5)
        int startRange = Integer.MIN_VALUE;
        int endRange = Integer.MIN_VALUE;
        
        // (6)
        for(int i = 0; i<list.size(); i++) {
        
            // (7)
            if( i == 0){
                startRange = list.get(i).start;
                endRange = list.get(i).end;
                count++;
                continue;
            }else {
                // (8)
                int start = list.get(i).start;
                int end = list.get(i).end;
                // (8-1)
                if(start > endRange){
                    startRange = start;
                    endRange = end;
                    count++;
                }
                // (8-2)
                else if(start > startRange && end < endRange) {
                    startRange = start;
                    endRange = end;
                }
            }
        }

        // (9)
        int answer = count;
        return answer;
    }
}

// (1)
class CarRoute implements Comparable<CarRoute> {

    int start;
    int end;
    
    public CarRoute(int start, int end){
        this.start = start;
        this.end = end;
    }

    // (2)
    @Override
    public int compareTo(CarRoute o) {
        return this.start - o.start;
    }
}