[프로그래머스 lv3] 단속카메라 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

routes를 탈출지점을 기준으로 오름차순으로 정렬한다.

가장 첫번째 카메라의 위치를 routes[0][1]로 두고, 사용한 카메라의 개수를 1 증가시킨다.

routes를 1번 인덱스 부터 순회하면서 해당차량의 진입 지점과 마지막 카메라 위치를 비교한다.

 

1) 진입 지점이 마지막 카메라 위치보다 작거나 같으면, 마지막으로 설치한 카메라를 만나게 되므로 패스한다.

2) 진입 지점보다 마지막 카메라 위치보다 크면 이전에 있는 카메라로는 단속할 수 없으므로 새로운 카메라를 설치해야 한다. 카메라 설치 위치는 현재 차량의 탈출 지점이 가장 유리하므로 routes[i][1]을 마지막 카메라 위치로 설정한다. 이때, 사용한 카메라 개수를 1 증가시킨다.

 

마지막 routes[i]까지 순환한 후 사용한 카메라 개수를 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

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

    sort(routes.begin(), routes.end(), cmp);

    int x = routes[0][1], cnt = 1;
    for (int i=1; i<routes.size(); i++) {
        if (routes[i][0] <= x) continue;
        x = routes[i][1];
        cnt++;
    }

    return cnt;
}