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

단속카메라 (Level 3)

문제

전체 문제 보기

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

접근법

이 문제에서 구해야 하는 값은 전체 차량의 이동경로가 주어졌을 때 모든 차량이 한 번은 단속용 카메라를 만나도록 하기 위한 최소 카메라 설치대수이다. 차량의 이동 경로는 아래와 같이 규칙 없이 입력될 수 있다.

▲ 그림 1

카메라를 가장 최소한으로 설치 하기 위해서는 "가능한" 시작 지점에서 최대한 떨어진 곳에 설치하고, 그다음 카메라는 한번 설치한 카메라와 "가능한" 가장 멀리 떨어진 곳에 설치해야 한다. 그러면 "가능한" 이라고 추상적으로 표현한 부분을 어떻게 구체화 할 수 있을까? 

 

먼저 가장 시작 지점에서 최대한 멀리 떨어진 곳에 카메라를 설치하기 위해서는 가장 먼저 고속도로에서 진출하는 차량을 파악하여 그 차량이 고속도로를 진출하기 직전에 설치해야한다. 때문에 다음과 같이 진출 지점을 기준으로 오름차순 정렬이 필요하다.

▲ 그림 2

첫 카메라는 아무리 늦어도 1번 차량이 빠져나가는 위치에는 있어야 한다. 때문에 첫 번째 카메라 아래의 표시된 위치에 설치하는 것이 좋을 것이다. 

▲ 그림 3

해당 위치에 카메라를 설치하면 2번, 3번, 6번 차량도 해당 카메라와 만나게 된다. 그렇다면 그 다음 카메라가 필요한 위치는 어디일까? 방금 카메라가 설치된 위치 이후에 진입한 차가 나가기 전에는 새로운 카메라가 설치되어야 할 것이다. 즉, 첫 번째 차량의 진출 시점보다 늦게 진입한 차량이 나올때 까지 탐색을 실시한다. 4번 차량이 방금 설치한 위치 이후에 진입하였다. 그럼 다음 카메라는 어디에 설치해야 할까? 방금 설치한 카메라와 가능한 멀리 설치하는 것이 좋지 않겠는가? 하지만 4번 차량이 나가기 전에는 카메라가 하나쯤은 있어야 할 것이다.

▲ 그림 4

두 번째 카메라의 위치는 4번 차량이 진출하는 위치에 설치하는 것이 적당할 것이다. 그 다음 위치는 어디가 좋겠는가? 두 번째 카메라 이후에 진입한 차량이 나가기 전에는 카메라를 설치해야 하지 않겠는가? 즉, 7번 차량이 나가는 위치에 세 번째 카메라가 필요할 것이다.

▲ 그림 5

이렇게 최소한 총 3대의 카메라가 필요하다는 것을 알 수 있다. 이 알고리즘의 시간복잡도를 따져보자. 차량의 대수를 \(n\)이라고 했을 때 처음 정렬을 위해서 \(O(n log n)\)이 소요되고, 카메라의 위치를 탐색하기 위해서는 전체 차량을 한 번만  탐색하면 되기에 \(O(n)\)이 소요된다. 때문에 전체 시간 복잡도는 \(O(n log n)\)이고, 최대 차량의 수가 \(10,000\) 대 정도이기 때문에 사용 가능한 방법이라 할 수 있다.

구현

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

using namespace std;
bool Compare(const vector<int>& left, const vector<int>& right)
{
    return left[1] < right[1];
}
int solution(vector<vector<int>> routes) {
    int answer {0};

    // 차량 진출 시점을 기준으로 오름차순 정렬
    sort(routes.begin(), routes.end(), Compare);

    // 카메라 설치 위치 초기화
    int cameraLocation {-30'001};

    auto iter = routes.begin();   
    while(iter != routes.end())
    {
        // 새로운 카메라가 필요한 경우
        if((*iter)[0] > cameraLocation)
        {
            cameraLocation = (*iter)[1];
            answer++;
        }
        iter++;
    }

    return answer;
}