(C++) - 프로그래머스(고득점 kit - Greedy) : 단속카메라

programmers.co.kr/learn/courses/30/lessons/42884

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

회의실 배정 문제와 같은 방식의 문제였습니다.

 

풀이방법

 1. 고속도로에서 나가는 지점이 빠른 순으로 routes를 정렬해줍니다.

 2. 고속도로의 전체 길이를 빠르게 탐색하기 위해서는 나가는 지점만 비교하는 것입니다.

 O(n)으로 routes의 원소를 나가는 지점만 비교해 지나가는 자동차의 수 가장 많이 겹치는 지점마다 answer변수를 더합니다. 어떤 자동차를 골랐을 때 그 자동차가 나가는 지점이 가장 빠르다면 그 지점보다 작은 지점에서 출발하는 모든 자동차를 단속할 수 있습니다. 따라서 해당 자동차의 지점 이전에 설치한 카메라 1개로 모두 볼 수 있습니다.

 

Code

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int cmp(vector<int> a,vector<int> b){
    return a[1] < b[1];
}
int solution(vector<vector<int>> routes) {
    int answer = 0;
    int end = -30001;
    sort(routes.begin(),routes.end(),cmp);

    for(int i = 0; i < routes.size(); i++){
        int start = routes[i][0];
        if(end < start) {
            answer++;
            end = routes[i][1];
        }
    }
    
    return answer;
}