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

 

문제 링크: programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

 

풀이

 

나는 처음에 차량을 진입 시점이 빠른 순서대로 정렬해서 문제를 풀었는데, 다른 사람들의 풀이를 보니 진출 시점이 빠른 순서대로 정렬 후 문제를 푸는게 더 간단했다. 

 

• 진출 시점이 빠른 순서대로 차량을 정렬한다. 
• 1) 차량의 진입 시점이 camera보다 앞에 있다면(작거나 같다면)
    => 차량 경로가 camera 위치에 포함되므로 추가 카메라 설치 필요 없음
  2) 차량의 진입 시점이 camera보다 뒤에 있다면(크다면)
    => 현재 차량의 진출 시점에 다른 카메라를 설치해야 함

 

 

 

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
 
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 camera = -30001;
    sort(routes.begin(), routes.end(), cmp); // 진출 시점이 빠른순
    for(int i = 0; i < routes.size(); i++){
        if(camera < routes[i][0]){
            answer++;
            camera = routes[i][1];
        }
    }
    return answer;
}

 

테스트 결과