프로그래머스. 단속카메라(c++) / 그리디(Greedy)

이 문제는 도저히 아이디어가 생각나지 않아 코드는 참고하지 않고 아이디어만 다른 분의 아이디어를 참고해서 풀었다.

아래가 다른 분의 아이디어이다.

 

[메인 로직]

첫 번째 카메라는 첫 번째로 차가 빠져나가는 지점에 설치해야 합니다. 왜냐하면 이 지점에서 설치하지 않으면 첫 번째로 빠져나가는 차는 찍을 수 없기 때문입니다. 그 지점에 카메라를 설치하면 해당 지점을 지나는 차들은 모두 카메라에 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.

두 번째 카메라는 아직 카메라에 찍히지 않은 차 중에서 첫 번째로 차가 빠져나가는 지점에 설치하면 됩니다. 두 번째 지점에 카메라를 설치하면 해당 지점을 지나는 차량들은 모두 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다.

이런 식으로 계속 해서 카메라를 설치하는 과정을 거치면 됩니다. 요점은, 카메라가 설치 되었을 때, 더 이상 신경쓰지 않아도 되는 차량들을 확실하게 고려하지 않는 방식으로 프로그래밍을 해야 한다는 것입니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int solution(vector<vector<int>> routes) {
    int answer = 0;
    vector<vector<int>> v;
    int check[10001] = {0, };
    
    for(int i=0; i<routes.size(); i++){
        vector<int> temp;
        temp.push_back(routes[i][1]);
        temp.push_back(routes[i][0]);
        v.push_back(temp);
    }
    
    sort(v.begin(), v.end());
        
    for(int i=0; i<v.size(); i++){
        if(check[i]) continue;
        int num = v[i][0];
        answer++;
        for(int j=0; j<v.size(); j++){
            if(v[j][1]<=num && num<=v[j][0]){
                check[j] = 1;
            }
        }
    }
    
    return answer;
}