[Programmers/C++] 단속카메라

시간 복잡도

• 정렬과 순차 탐색이 필요하므로 $O(NlogN)$의 시간 복잡도가 발생합니다.

문제 접근법

• 차들의 진입 시점을 기준으로 정렬합니다.
• 이후 첫 번째 카메라를 첫 번째 차량이 고속도로에서 나가는 시점에 놓았다고 가정하고 다음 차량의 진입 시점에 따라 어떻게 놓을지 결정합니다.

• 위 그림과 같이 3가지의 경우가 있습니다.
• 1번의 경우 카메라의 위치를 바꾸지 않아도 됩니다.
• 2번의 경우 빨간색 지점에 설치하면 다음 차량이 단속카메라에 찍히지 않기 때문에 파란색 지점으로 카메라의 위치를 옮겨주어야 합니다.

  if(out >= v[1])
     out = v[1];

• 3번의 경우 카메라를 1대 더 설치해주어야 합니다.

  // out은 차량이 나가는 시점
  // v는 다음 차량
  if(out < v[0])
  {
     answer++; // 카메라 1대 추가 설치
     out = v[1]; // 카메라의 위치를 새로 들어온 차량이 나가는 시점에 설치
  }

코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    
    sort(routes.begin(), routes.end());
    
    int out = routes[0][1];
    
    for(vector<int> v : routes)
    {
        if(out < v[0])
        {
            // 차가 나가기 전에 새로운 차가 들어옴
            answer++;
            out = v[1];
        }
        
        if(out >= v[1])
        {
            // 새로 들어온 차가 먼저 나가면
            out = v[1];
        }
    }
    
    
    return answer;
}