단속카메라

문제

문제의 시간복잡도

n값이 10000개 이다. 따라서 break문이 있는 $O(n^2)$ 정도의 시간에는 해결 할 수 있다고 생각을 했다.

접근법

routes를 첫번째 요소를 기준으로 sort를 하여서 가장 외곽을 지난 자동차부터 카메라로 탐색을 해야 한다고 생각했다.
결국에는 모든 자동차가 한번씩 카메라에 찍혀야 하기 때문에 앞쪽부터 탐색을 해주는 것이다.

이 맨 앞쪽 자동차를 찍기 위해서는 카메라가 필요하다. 그런데 이 카메라를 설치한 김에 뒤에 애들도 확인하는 것이 좋을 것이다.

그렇게해서 다음 애들이 앞에 자동차가 지나간 길을 한번이라도 지나갔는가를 판단한다.

그리고 그 지나간 자동차의 두번째 인덱스 경계와 맨 처음 선택했던 자동차가 지나간 경로의 끝 경계를 비교한다. 그 값중에서 작은 값을 경계로 삼는다.

이렇게 해주는 이유는 모든 자동차가 지나가는 경로에 카메라를 설치하기 위함이다.

그렇게해서 범위를 확인하다가 이를 초과하는 녀석이 있을 것이다. 그경우에는 카메라를 하나 더 설치해주어야 하는 경우이다.

이를 routes 안의 모든 원소들을 탐색할 때 까지 반복을 해준다.

풀이

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

using namespace std;

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


int solution(vector<vector<int>> routes) {
    int answer = 1, idx = 0;
    sort(routes.begin(),routes.end(),compare);
    int add_idx = 1;
    
    while(1)
    {
        if(idx+add_idx > routes.size()-1)
            break;
        
        if(routes[idx+add_idx][0] <= routes[idx][1])
        {
            if(routes[idx][1] > routes[idx+add_idx][1])
            {
                routes[idx][1] = routes[idx+add_idx][1];
            }
            add_idx++;
        }
        else
        {
            idx += add_idx;
            add_idx = 1;
            answer++;
        }
    }
    
    
    return answer;
}

/*

단속용 카메라에 한번은 무조건 만나야된다. 이 차들이

고속도로를 이동하는 차량의 경로 routes

최대 몇대의 카메라를 설치해야 하는가?

routes의 하나의 요소는 2개의 인덱스 요소를 가짐.
첫번째는 시작지점 두번째는 나가는지점 (나가는 지점이 더 크네)

진입, 진출 지점은 6만 1개 (1을 단위로 이동이 가능하다)

인덱스 중 첫번째 인덱스를 기준으로 오름차순 sort를 한다. 두번째도 오름차순으로 sort한다.

그리고 앞쪽부터 요소를 보면서 하나의 요소를 선택한다. 그리고 다음 요소가 그 앞에 요소에 속하는지를 본다.
그렇게 해서 선택한 요소에 속하지 않는 경우에는 answer값을 하나 늘려준다.

빼먹은 점 한가지는 요소를 비교를 하던 중에 뒷 요소의 뒤쪽 경계가 더 짧다면 뒤쪽 경계로 경계를 변경해주어야 한다.

*/