[프로그래머스 고득점 kit] 단속 카메라 c++ ( 구간, greedy )

문제 링크

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

프로그래머스

 

문제 풀이

최대한 중복이 많이 발생하는 구간마다 카메라를 설치해나가면 된다.

시작 시간, 종료시간이 작은 순서로 정렬한 뒤, 현재 route와 다음 route 사이에 중복 구간이 존재하는지 확인한다. 만약 존재한다면, 현재 구간과 새롭게 편입한 route의 중복 구간을 구한 뒤, 다음 route를 통해 또다시 중복구간이 형성되는지 확인한다.  최대한 많은 자동차가 겹칠 수 있는 중복기간을 찾은 뒤, 더이상 중복 구간이 형성되지 않는다면 해당 구간 사이에 카메라를 비치하는 것으로 여태까지 중복 구간안에 포함 된 모든 자동차를 체크할 수 있다. 

 

정답 코드

#include <string>
#include <vector>
#include<algorithm>
#include<math.h>
using namespace std;
bool cmp(vector<int> a, vector<int> b){ //빠른 시작, 빠른 종료 부터
    if(a[0]!=b[0])return a[0]<b[0];
    return a[1]<b[1];
}
int solution(vector<vector<int>> routes) {
    int answer =0;
    sort(routes.begin(),routes.end(),cmp);
    int idx=0;
    while(idx<routes.size()){ //가장 앞에있는 루트 부터 시작
        int now=idx;
        answer++;
        int st=routes[now][0],ed=routes[now][1];
        for(int i=now+1;i<routes.size();i++){ 
            //중복 구간안에 포함되면, 카메라를 새로 설칫할 필요 없다.
            if(routes[i][0]<=ed&&routes[i][1]>=st){ 
                //중복 구간을 점차 좁혀 나간다. 
                st=max(routes[i][0],st);
                ed=min(routes[i][1],ed);
                idx=i;
            }
        }
        idx++;
    }
    
    return answer;
}