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

 

 

문제

문제 설명

 

 

[문제 요약]

​

특정 구간을 지나는 모든 차량이 단속용 카메라를 만다록 하는 문제다.

 

이전에 풀었던, 요격 시스템이라는 문제와 매우 비슷하다. 

[프로그래머스/Python] 요격 시스템

 

 

풀이

 

이 문제는 greedy 하게 풀 수 있다. 특정 구간을 지나서 무조건 새로 카메라를 달아야 하는 구간이 오면 새로 비교하던 데이터들을 갱신하고, 다시 카메라가 차량들을 단속할 수 있는지 판단하면 된다.

 

이전에는 시작점을 기준으로 정렬을 해서 풀었는데, 마지막 점을 기준으로 풀 수도 있어서 방법을 바꿔 끝점을 기준으로 문제를 풀어보려고 한다.

 

끝 점을 기준으로 정렬을 하면 정렬된 수들은 시작점이 현재 끝점보다 작으면 같은 구간에서 지울 수 있다.

 

왜냐하면 이전에 저장된 끝점의 범위는 정렬이 되어있으므로 다음에 for문에서 나올 차량의 구간보다 무조건 끝점의 범위가 작기 때문이다.

그래서 시작점의 위치가 현재 저장된 끝점보다 작으면 하나의 카메라로 차량의 단속이 가능하다는 뜻이다.

  

​

[아이디어 정리]

1. 차량의 경로를 경로의 끝점을 기준으로 정렬한다.
2. 현재 저장된 끝점의 변수보다 시작점의 변수가 작으면 현재 카메라로 단속이 가능하므로 pass한다.
3. 만약 현재 저장된 끝점의 변수보다 시작점의 변수가 크면, 새로 카메라를 달아야 하므로 끝점을 갱신하고 카메라 수를 1개 올린다. 
4. 총 카메라 수를 return하면 된다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(vector<int> a, vector<int>b)
{
    return a[1]<b[1];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    sort(routes.begin(), routes.end(),compare);
    int nowFinalRoute=-30001;
    for (int i=0; i<routes.size(); i++)
    {
        if (nowFinalRoute<routes[i][0])
        {
            answer++;
            nowFinalRoute=routes[i][1];
        }
    }
    return answer;
}

 

---

 

끝점을 기준으로 하면 조건이 약간 줄어들게 된다

이전에 푼 문제랑 완전 똑같은 문제라 쉽네...

 

프로그래머스