[그리디, 난이도 중] 프로그래머즈, 단속카메라

이 문제 같은 경우에는 차량들의 진출 지점을 기준으로 오름차순으로 정렬해야 한다.

그리고 최근에 설치한 카메라의 지점을 기록하는 변수(recent_camera) 가 필요하다.

 

입출력 예

 

정렬 전

정렬 후

첫 차량(정렬 후)의 진출 지점에 카메라를 설치한다. (recent_camera=-13, answer=1)

두 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-13)

세 번째 차량의 진입 지점은 recent_camera의 이후이므로 진출 지점에 카메라를 설치한다. (recent_camera=-3)

네 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-3)

 

이렇게 2번째 차량부터는 최근 설치한 카메라 지점과 진입 지점을 비교하여,

recent_camera>진입 지점 이라면 그냥 넘기고,

진입 지점> recent_camera 이라면 진출 지점에 카메라를 설치하고(recent_camera=진출 지점), answer을 1증가시켜준다.

이를 반복하면 문제가 해결된다.

n을 차량의 대수라고 했을 때, 이 소스 코드의 시간복잡도는 sort의 시간 복잡도인 O(nlogn)과 같다.

 

정확성, 효율성 만점

 

#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> a, vector<int> b){
    return a[1]<b[1];
}
int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(),routes.end(),compare);
    int recent_camera = routes[0][1];
    for(int i=1;i<routes.size();i++){
        if(recent_camera<routes[i][0]){
            answer++;
            recent_camera = routes[i][1];
        }
    }
    return answer;
}