단속카메라 42884

문제

접근 방법

일단 입출력 예를 그려보기로 했다.

무언가 법칙이 있는 것 같지만, 모르겠었다. 하나 더 만들어보기로 했다.

무언가 끝과 관련 있어 보이긴 했지만 모르겠다. 끝에 집중해보았다.

가장 짧은 끝에 집중하면 되는 것 같았다. 시작 시간이 다른 경우도 생각해봐야 했다.

가장 늦게 진입하고 가장 빨리 진출하는 차량의 끝점이 중요한 것 같았다.

하나를 더 추가해보았다.

하나를 더 추가해보았다. 새로운 차량의 진입 시간이 기존 차량의 진출 시간을 넘어가면 새로운 감시 카메라를 달고 진출 시간을 더 짧은 것으로 갱신해주면 된다는 것을 알게 됐다.

코드

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

int solution(vector<vector<int>> routes)
{
    int answer = 0;
    int right = -30001;
    sort(routes.begin(), routes.end());
    for (vector<int> r : routes)
    {
        if (right < r[0])
        {
            ++answer;
            right = r[1];
        }
        else
        {
            if (right > r[1])
                right = r[1];
        }
    }
    return answer;
}

풀이

진입 시간 순서대로 정렬해주고 진출 시간을 계속 갱신시켜주며 진입 시간이 진출 시간을 넘어가면 단속 카메라의 범위를 넘어갔다는 뜻이므로 단속 카메라 개수를 증가시켜주고 진출 시간을 갱신해 준다.