[프로그래머스] 단속카메라(C++)

문제 링크

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

프로그래머스

 

 

코드 구현

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

using namespace std;

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

int solution(vector<vector<int>> routes) 
{
    int answer = 1;
    
    // 진출 시점 기준으로 오름차순 정렬
    sort(routes.begin(), routes.end(), Compare);

    int out = routes[0][1];

    for (const auto& route : routes)
    {
        if (out >= route[0] && out <= route[1]) continue;
        else
        {
            out = route[1];
            answer++;
        }
    }

    return answer;
}

 

 

해결 방법

---

• 진출 시점을 기준으로 오름차순으로 정렬
• 첫 번째 진출 시점에 카메라를 설치하고 다음 차량들을 순회하면서 카메라가 다음 차량의 범위 안에 없으면 카메라를 추가한다