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

문제 링크

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

 

 

 

풀이

 

카메라 위치는 차량의 진입 시점으로 하되,

1. 카메라 위치를 갱신(카메라 개수 일정)

2. 카메라 개수 추가(카메라 개수 증가)

이렇게 나누었고,

 

카메라 개수를 추가하는 것에 대한 임계값을 차량의 나간 시점으로 하였다.

(반복문을 돌면서 카메라를 최소 개수로 설치해야 하므로)

 

// init

나간 시점으로 오름차순 정렬 --- 나간 시점(임계값)이 작은 것부터 비교해야 하므로

임계값 -30001로 초기화(차량 진입 시점은 -30000 이상이므로)

--- 반복문을 0부터 돌면서 처음에 카메라 개수를 추가하기 위함

 

// process

반복문(모든 차량에 대해서)

{

    i번째 차량의 나간 시점이 임계값을 안넘었으면? = 카메라를 추가안하고 위치만 갱신해도 되면? --- continue;

    (이 때, 카메라 위치는 차량의 진입 시점이다. --- 카메라 위치를 묻는 문제가 아니므로 머릿속으로만 생각)

    넘었으면? ---

    1. 카메라 개수 추가(answer++;),

    2. 임계값 갱신(i번째 차량의 나간 시점)

}

 

return answer;

 

 

 

 

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

using namespace std;

// 차량의 경로 routes
// 모든 차량이 한 번은 단속용 카메라를 만나도록 최소 몇 대의 카메라 설치
// routes[i][0]은 고속도로에 진입한 지점
// routes[i][1]은 고속도로에 나간 지점

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

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    // init
    sort(routes.begin(), routes.end(), cmp);         // 나간 시점을 기준으로 오름차순
    int thres = -30001;         // 임계값
    
    // process
    for(int i=0; i<routes.size(); i++){
        int start = routes[i][0];       // 진입 시점
        int end = routes[i][1];     // 나간 시점
        if(thres >= start) continue;       // 카메라 위치 갱신(해당 차량의 진입 시점)
        answer++;           // 카메라 대수 추가(카메라 위치는 차량 진입 시점)
        thres = end;       // 해당 차량의 나간 지점으로 임계값 갱신
    }
    
    return answer;      // 설치할 카메라 수의 최솟값 리턴
}