단속카메라 (프로그래머스)

그리디 알고리즘을 사용하는 문제였다. 

 

차들이 공통적으로 사용할 수 있는 카메라의 수를 부분적으로 찾아야 한다. 그러기 위해서는 우선 차량의 진입 지점을 오름차순으로 정렬해줘야 한다. 

 

어떠한 경우더라도 단속 카메라는 1개 이상은 설치되어야 하므로 answer는 1부터 시작한다. 

 

정렬한 상태에서 자동차들의 진입 진출 범위는 다음과 같다.

 

처음 진입하는 차량은 15까지 진출을 하기 때문에 적어도 15에는 카메라가 배치되어야 한다. (이 카메라는 최초로 배치해야 할 카메라이다. 즉, answer의 1에 대한 카메라를 배치하는 과정인 것이다.)

 

하지만 다음 차량이 -13까지 진출하기 때문에 최소의 카메라 배치를 만족하기 위해 카메라의 위치는 -13에 위치하게 된다. 

 

이렇게 하면 첫번째, 두 번째 차량이 진입 진출하는 범위 내에서 단속카메라를 설치한다는 조건을 모두 만족할 수 있게 된다. 이제 세 번째 차량을 살펴보자. 진입 진출 시점이 -14부터 -5까지 이다. 앞에서 했던 것처럼 카메라를 -5에 놓으면 두 번째 차량이 단속카메라 범위에 없으므로 단속을 할 수 없게 된다. 

 

그러므로 카메라는 -14에 배치해줘야 한다. 그러면 1, 2, 3번째 차량 모두 범위 내에 있어 단속할 수 있게 된다.

 

이제 4번째 차량을 살펴보자 3번째 차량 범위와 -5를 맞닿아 있다. 하지만 카메라를 -5로 옮기면 두번째 차량을 단속할 수 없게 된다. 

 

이 경우는 카메라를 어떻게 배치하든 방법이 없으므로 새로운 카메라를 배치해야 한다. 배치하는 위치는 네번째 차량의 진출 시점 -3에 배치한다. 

 

이제 모든 차량에 대한 카메라 단속이 가능하게 되었다. 이 예제에서는 총 2개의 단속카메라가 필요하다.

 

코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> routes) 
{
    int answer = 1; // 배치해야할 최소한의 단속카메라(첫번째 단속카메라)
    sort(routes.begin(), routes.end());
    int camera = routes[0][1]; 
    for(int i = 0; i < routes.size() - 1; ++i)
    {
        // 이전 카메라가 차량 진출시점보다 더 멀리 있는 경우
        // 카메라를 차량 진출 시점으로 땡겨준다.
        if(camera > routes[i][1]) camera = routes[i][1];
        // 하지만 다음 차량 진입 시점이 카메라보다 큰 경우
        if(camera < routes[i + 1][0]) 
        {
            // 어떻게 배치하여도 만족할 수 없는 경우로 
            // 카메라를 새로 배치해야 한다.
            ++answer;
            camera = routes[i + 1][1];
        }
    }
    return answer;
}