프로그래머스 단속카메라

문제

https://programmers.co.kr/learn/courses/30/lessons/42884

코드

#include <string>
#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 = 0;
    sort(routes.begin(),routes.end(),compare);
    
    while(!routes.empty()){
        int position=routes[0][1];
        answer++;
        for(int i=0;i<routes.size();i++){
            if(routes[i][0]<=position&&position<=routes[i][1]){
                routes.erase(routes.begin()+i);
                i--;
            }
        }        
    }
    
    return answer;
}

풀이

그리디 알고리즘 문제로 그리디는 매 순간에서 최선의 선택을 해서 답을 찾아가는 알고리즘입니다.

문제에서는 차량의 경로를 주고 모든 차량이 한번씩은 단속카메라에 걸치게 하되 최소한의 단속카메라 수를 요구합니다. 차량의 경로 끝부분이 가장 적은 지점에 단속카메라가 항상 필요다는게 뽀인트입니다.

예를 들어서 입력이

vector<vector<int>> routes={{4,5},{2,5],{0,4},{11,13}};

이렇게 들어왔을 경우 표를 그려봤습니다

보시면 가장 빨리 경로가 끝나는 3번째 차의 마지막 부분 4에는 필수적으로 감시카메라 한대가 필요합니다 왜냐하면 그 이후에 카메라를 달면 3번째 차는 감시를 할 수가 없기 때문이져~

따라서 routes를 경로 끝부분을 기준으로 오름차순으로 정렬 시킨 후에 겹치는 경로들을 제거하면서 카운팅 해주면 됩니다.