[프로그래머스]탐욕법(Greedy) : 단속카메라 (level 3)(c++)

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

코딩테스트 연습 - 단속카메라

 

 

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

using namespace std;

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

    // 끝점을 기준으로 오름차순 정렬
    sort(routes.begin(), routes.end(), [](vector<int> &a, vector<int> &b) {
        return a[1] < b[1];
        });
    
    /*
        카메라를 설치하는 기준
        : 기준끝점(std_end)이 다음차의 시작점보다 작을 때 (=영역이 겹치지 않을 때)
        기준끝점에 카메라를 설치한다.
    */

    // 아직 카메라를 만나지 못한 차의 end점
    int std_end = routes[0][1];
    int camera = 0;

    for (int i = 0; i < routes.size(); ++i)
    {
        // std_end점과 현재 차의 영역이 겹치지 않는다면
        if (std_end < routes[i][0])
        {
            ++camera;
            std_end = routes[i][1];
        }
    }
   
    // 마지막 end점에 카메라 설치
    return camera + 1;
}

 

 

그리디적인 사고 : 그때그때의 상황에서의 최선의 선택을 한다.

 

이 문제에서 그리디적인 생각은

아직 카메라를 만나지 못한 차량의 영역과 다음 차의 영역이 겹치지 않는다면

그때 카메라를 하나씩 설치하는 것이다.

 

 

 

그리디 문제는 늘 아이디어 자체를 떠올리기가 힘든 것 같다.

연습을 더 해야겠다 ㅠㅠ