[C++]단속카메라

요약

• routes 오름차순 정렬
• 카메라 범위 설정풀이과정순서대로 routes를 체크하기 위해 sort해준다.
  예제[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]의 경우
  [[-20,-15], [-18,-13],[-14,-5],[-5,-3]] 으로 정렬한단 얘기
  이후 각 자동차마다 camera 설치 가능 범위를 정한다.

맨 처음 자동차를 감시할 수 있는 범위

두번째의 경우 (-18,-15)로 줄어든다.

세 번째의 경우 더이상 하나의 카메라로 감시할 수 없게 됐다.

검사 조건은 camera 범위의 end값과 routes[i][0] 값을 비교하면 된다.

이런 식으로 구현하였다.

코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    int start = 0;
    int end = 0;
    bool cam = false;
    sort(routes.begin(), routes.end());
    for(int i = 0; i < routes.size(); i++)
    {
        if(routes[i][0] > end)
        {    //현재 범위(start,end)를 벗어나는 차량
            cam = false;
            answer++;
        }

        if(cam == false)    //새로운 카메라 범위 시작
        {
            cam = true;
            start = routes[i][0];
            end = routes[i][1];
        }
        else    //카메라 범위 업데이트
        {
            start = routes[i][0];
            end = min(end, routes[i][1]);
        }
    }
    return answr;
}

기억할 점

다른사람의 풀이

나는 시작점 정렬로 풀었는데, 끝점 정렬로 풀면 범위 start, end에서 start가 필요치 않다. camera의 마지막 부분과 routes[i][0]을 비교하고, 필요에 따라 routes[i][1]로 start를 갱신해주면 된다.  bool 변수도 없이 구현이 가능하다.

#include <bits/stdc++.h>

using namespace std;

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

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