프로그래머스: 단속카메라

문제 설명

• 모든 자동차를 감시하는 카메라를 설치해야 합니다. 카메라를 최소한으로 설치하는 방법을 구하는 문제입니다.
• 저는 해당 좌표에 길이만큼 놓여 있는 막대기들을 몇개의 꼬챙이를 사용하면 다 꾈수 있을까를 구하는 문제와 같다고 생각했습니다.
  

접근법

• 활동 선택 문제 - 그리디 알고리즘 문제입니다.
• 고속도로에서 나간 지점을 기준으로 정렬합니다.
• 정렬된 순서대로 차량을 순회하면서 다음을 진행합니다.
  • 비교군이 없다면 비교군을 하나 선택합니다.
  • 비교군의 나간 지점보다 진입 지점이 낮은 자동차는 하나의 카메라로 단속할 수 있습니다.
    • 정렬을 했기 때문에 기준값이 바뀌지 않습니다.

정답

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        //고속도로에서 나간 지점을 기준으로 정렬합니다.
		Arrays.sort(routes,new Comparator<int[]>(){
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		
		//비교군을 넣기 위해 queue를 생성했습니다.
		Queue<int[]> q = new LinkedList<>();

		for (int i = 0; i < routes.length; i++) {
			if(q.isEmpty() == true) { //비교군이 아무것도 없다면
				q.add(routes[i]); // 비교군을 하나 설정합니다
				answer++;
			}
			if(q.isEmpty() == false) { // 비교군이 있다면 비교를 진행합니다.
	            // 비교군의 나간 지점보다 i번째 자동차의 진입 지점이 낮다면 
                // 여전히 하나의 카메라로 단속이 가능합니다.
				if(q.peek()[1]>= routes[i][0]) continue; 
                //위 조건을 만족하지 못한다면 비교군을 교체합니다.
				q.poll(); 
				q.add(routes[i]);
				answer++; 
					
			}
		}
        return answer;
    }
}

기타

• 시작시간을 기준으로 정렬하면 어떻게 될까요?
  다음의 사진을 보면서 생각해 봅시다.
  
  시작시간으로 정렬했을 때에는 기준값을 계속 업데이트 해야 합니다.시작시간으로 했을 때 기준값은 겹쳐진 값들의 시작시간 최댓값 ~ 겹쳐진 값들의 종료시간 최소값이 됩니다.

하지만 종료시간을 기준으로 정렬하면 기준's 종료시간>= 비교값's 시작시간만 고려하면 됩니다.

그 이유는 다음과 같습니다.
정렬을 하지 않고 기준's 종료시간>= 비교값's 시작시간만 생각하면 다음과 같은 문제가 발생합니다.

• 회색은 그림에서의 실제 크기가 아니라 우리가 모르는 부분이라고 생각해 주세요.
  • 회색이 충분히 길다면 두 블록은 하나로 묶을 수 있습니다.
  • 하지만 그림처럼 회색이 짧으면 두 블록은 하나로 묶을 수 없습니다.
  • 종료시간을 기준으로 정렬하면 회색의 끝부분이 반드시 이전블록, 혹은 기준블록보다 더 뒤에 있어야 합니다.