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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

그리디 알고리즘을 사용해서 풀 수 있다. 우선 routes를 오름차순으로 정렬하면 진입지점이 가장 빠른 순서대로 정렬된다. 그 상태에서 첫 번째 차량을 기준으로 잡고 다음 차량부터 비교해준다. 다음 차량이 기준점보다 먼저 고속도로를 빠져나가면 기준점의 위치를 변경한다. 다음 차량의 진입 지점이 기준점보다 나중이라면 기존의 CCTV로는 해당 차량을 감시할 수 없기 때문에 CCTV 개수를 늘리고 해당 차량의 진입점을 기준으로 한다.

코드

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

int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(), routes.end());
    int pos = routes[0][1];
    for (int i = 1; i < routes.size(); i++) {
        if (pos > routes[i][1])
            pos = routes[i][1];
        else if (pos < routes[i][0]) {
            answer++;
            pos = routes[i][1];
        }
    }
    return answer;
}