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

문제

---

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

풀이

---

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는 지를 구하는 문제로, 탐욕법을 활용, 진출 위치를 기준으로 정렬하여 순차적으로 카메라를 설치한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmd(vector<int> a, vector<int> b)
{
    return(a[1] < b[1]);
}

int solution(vector<vector<int>> routes) 
{
    int answer = 0;

    vector<vector<int>> mod_route = routes;

    sort(mod_route.begin(), mod_route.end(), cmd);
    //진출기준

    int camera = -30001;

    for (int i = 0; i < mod_route.size(); i++)
    {
        if (mod_route[i][0] > camera)
        {
            answer++;
            camera = mod_route[i][1];
        }
    }
    return answer;
}