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

탐욕알고리즘 (Greedy)

N개의 차량의 진입지점과 진출지점이 주어지면 모든 차량을 단속할 수 있는 단속카메라의 최소 설치 개수를 반환하는 문제

 

접근방법

진출지점을 기준으로 먼저 나가는 차가 앞에 오도록 차들을 정렬한 후에,

첫번째 차 부터 이 차가 나가는 지점에 단속카메라를 설치한다고 할 때, 차례로 차를 순회하며 현재 단속카메라가 단속할 수 있는 차량인지 확인한다.

= 반복문에서 가리키고 있는 차의 진입지점이 현재 단속카메라의 위치와 같거나 그 전에 위치하면,

해당차는 이미 단속할 수 있으므로 넘어가고,

만약, 이 차의 진입지점이 현재 단속카메라의 위치보다 이후에 위치한다면, 해당 카메라로는 단속할 수 없으므로 다시 이 차의 진출지점에 단속카메라를 설치하고, 단속카메라의 총 개수를 1 추가한다.

 

이렇게 반복문이 종료되면 마지막 차량 묶음을 감시할 수 있는 단속카메라의 개수는 카운트되지 않았으므로 1을 더해서 반환한다.

 

오답노트

처음에 정렬을 진입지점을 기준으로 정렬했었는데, 그러면 첫번째 차량이 진출하기 전에 다음 차량이 진출해버리는 경우는 고려하지 못하기 때문에 진출지점을 기준으로 정렬해야 했다.

 

 

소스코드

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

using namespace std;

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

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), cmp);
    
    int e = routes[0][1];
    
    for(vector<int> route : routes){
        if(route[0] > e){
            e = route[1];
            answer++;
        }
    }
    
    return answer+1;
}