[프로그래머스] 단속카메라 [C++][lv.3]

코딩테스트 연습 - 단속카메라 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

#문제 간단 정리

그리디 문제기 때문에

구현보다 발상이 더 어렵다

 

#문제 해결 방법

우선 무조건 단속 카메라의 끝나는 지점으로 정렬해서

다음에 오는 시작지점이 현재 끝나는 지점에 바깥에 있다면 

단속 카메라가 하나 더 필요한거기 때문에 

 

단속카메라 개수를 1개 늘리고

마지막 지점 변수를 업데이트 해준다,

 

마지막 지점으로 체크한다는 발상이 어려운데

이 힌트를

각 구간을 전부 저장하는건 비효율적이고 너무 구현이 어렵기 때문에

더 좋은 방향을 자연스럽게 떠올리려는 것이 필요하다

 

#전체 코드

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

using namespace std;

int solution(vector<vector<int>> routes) {

    sort(routes.begin(), routes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    int cctv = 0;
    int lastCamera = -30001; 

    for (const auto& route : routes) {
        if (route[0] > lastCamera) { 
            lastCamera = route[1];
            cctv++;
        }
    }

    return cctv;
}