[프로그래머스] 단속카메라 / 탐욕법, Greedy / C++ 풀이

 

문제 링크

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

프로그래머스

 

풀이 전략

주어진 구간에 대한 배열 routes를 정렬하고 앞에서부터 구간이 겹치게 단속 카메라를 설치할 수 있는 구간을 찾는다.

주어진 예시 [[-20, -15], [-14, -5], [-18, -13], [-5, -3]] 로 생각해보자.

위를 정렬하면  [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]이고, 정렬된 routes를 앞에서부터 살펴보면서 구간이 겹쳐지도록 단속 카메라를 설치할 수 있는지 확인하면 된다. 

첫번째 구간과 두번째 구간에 대해 [-18, -15] 어딘가에 설치하면 두 구간 모두 감시할 수 있다. [-18, -15]와 세번째 구간 [-14, -5]는 겹쳐지는 구간이 없으므로 단속 카메라를 따로 설치해야 한다.

 

C++ 풀이

/*
https://school.programmers.co.kr/learn/courses/30/lessons/42884
*/
#include <string>
#include <vector>
#include <algorithm>
#define INF (99999)
using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    sort(routes.begin(), routes.end());

    /*
    [left, right] : 감시카메라 설치 구역
    */
    int left = INF;
    int right = -INF;
    for(const auto& r : routes) {
        int rl = r[0];
        int rr = r[1];
        
        if(right < rl) {
        /*
        [left, right]와 겹치지 못하는 구역이면 새로 감시 카메라 설치
        */
            answer++;
            left = rl;
            right = rr;
        }
        else {
        /*
		[left, right]와 겹칠수 있는 구역이면 left, right 범위를 현재 구간과 겹치도록 갱신
        */
            left = max(left, rl);
            right = min(right, rr);
        }
        
    }
    return answer;
}