프로그래머스 - 단속카메라 (Lv.3)

문제 설명

• 차량들의 고속도로 시작지점, 끝지점이 주어질 때 모든 차량들이 단속 카메라에 최소 한번은 만나도록 카메라를 설치한다.
• 최소가 되는 카메라 개수를 구하라.

구현(All Pass)

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

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int n = routes.size();
    
    // 진출 지점을 기준으로 오름차순 정렬
    vector<pair<int, int>> cars;
    for(int i=0; i<n; i++){
        cars.push_back(make_pair(routes[i][0], routes[i][1]));
    }
    sort(cars.begin(), cars.end(), cmp);
    
    answer = n;
    int cam_idx = cars[0].second;
    for(int i=1; i<n; i++){
        int start = cars[i].first;
        int end = cars[i].second;
        if(start<=cam_idx) 
            answer--;
        else 
            cam_idx = end;
    }
    
    return answer;
}

• 차량을 진출 지점 기준으로 오름차순 정렬을 한다.
• 카메라를 모든 차량의 진출 지점에 설치한다.(n개에서 시작)
• 차량을 탐색하면서 주행한 고속도로 구간 내에 이전 차량의 카메라가 있는지 확인한다.
  • 카메라가 있다면 현재 차량의 마지막 지점 카메라는 뺀다.
• 위 과정을 반복한다.