[프로그래머스][그리디][C++] 단속카메라

문제

프로그래머스 그리디 - 단속카메라 (Level 3)

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

 

---

문제 풀이

접근 방식

모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 구하는 문제이다.

어느 위치에 카메라를 설치하는 것이 좋은지 판단하기 위해 다음과 같이 구현하였다.

 

우선, 차량의 이동 경로를 오름차순으로 정렬하였다.

그 후, 처음 차량의 이동 구간의 시작과 끝을 start와 end로 지정하고,

다음 차량의 이동 구간이 start와 end 사이인지를 확인하였다.

 

구간 내에 있는 경우에는 end를 해당 구간의 끝 지점으로 바꿔주고,

이 과정을 반복하여 한 대의 카메라로 단속 가능한 모든 차량을 찾아주었다.

 

구간 내에 있지 않은 경우는 카메라를 추가 설치해야 함을 의미하기 때문에 카메라 수를 증가시키고,

start와 end를 새롭게 설정해주고 위의 과정을 반복해주며 답을 구하였다.

 

---

풀이 코드 - C++

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

using namespace std;

int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end());
    int len = routes.size();
    int answer = 1;
    int start = routes[0][0];
    int end = routes[0][1];
    for(int i = 1; i < len; i++) {
        if(routes[i][0]>= start && routes[i][0] <= end){
            if(end > routes[i][1])
                end = routes[i][1];
        }
        else{
            answer++;
            start = routes[i][0];
            end = routes[i][1];
        }
    }
    return answer;
}

실행 결과

실행 결과 : 100.0