[프로그래머스] 42884. 단속카메라 C++ / Python 풀이

코딩테스트 연습 → 탐욕법(Greedy) → Lv.3 단속카메라

알고리즘 문제를 많이 풀어본 사람은 문제 유형만 봐도 그리디(Greedy) 알고리즘을 사용한다는 것을 바로 판단해야 한다. 필자 또한 비슷한 유형의 문제들을 풀어본 경험으로 인해 그리디를 사용한 문제라는 것을 알았지만, 왜 그리디를 사용하는 것인가? 라는 주입식 교육의 폐해인 의문이 들어 풀이 방법을 함께 살펴보고자 한다.

풀이 방법

 

공식 예시와 함께 문제를 살펴보자. 먼저, 첫 번째 차량은 -20의 위치에서 진입하여 -15의 위치까지 달린다. 현재까지의 단속카메라 위치는 -20 ~ -15 사이의 어디든 설치해도 1개의 카메라만 설치하면 될 것이다. 

 

두 번째 차량은 [-14, -5]의 위치까지 달린다. 그림으로 봤을 때 첫 번째 차량과 겹치는 구간이 없는 것을 확인할 수 있다. 그러므로 감시 카메라는 [-20, -15] 사이의 하나, [-14, -5] 사이의 하나. 총 2개가 필요하다.

 

이제 세 번째 차량을 보자. 세 번째 차량의 고속도로 주행 구간은 [-18, -13]으로, 첫 번째 차량으로 인해 세워질 단속 카메라의 범위와 두 번째 차량으로 인해 세워질 범위와 모두 겹친다. 이는 곧 단속 카메라를 세울 범위를 [-18, -15]와 [-14, -5]로 줄이거나, [-20, -15]와 [-14, -5]로 줄이는 방법이 있다는 것이다. 일단 이 두 가지의 방법을 둔 채 다음 차량을 보자.

 

네 번째 차량의 위치는 [-5, -3]의 위치까지 달린다. 이전에 빨간색과 같이 단속카메라를 달 구간을 정했다면, [-14, -5]의 범위를 줄여 [-18, -15]와 [-6, -5]로 단속카메라 2개의 범위를 정할 수 있지만, 노락색과 같이 단속카메라 구간을 정했다면 이전에 정한 단속카메라 범위와 네 번째 차량의 주행 구간이 겹치지 않아 [-20, -15],[-14, -5], 그리고 [-5, -3]로 감시카메라를 하나 더 달 수 밖에 없을 것이다. 그러므로, 최소 단속카메라 설치 개수는 총 2개가 된다.

 

풀이 방식에서 최대 난제는 어떻게 감시카메라를 다는 여러 방법 중, 효율적으로 최소한의 감시카메라 개수를 찾냐는 것이다. 방법은 간단하다. 출발 구간이 앞선 순으로 정렬해 차량을 확인하면 된다. 감시카메라는 무조건 앞 구간에서 출발한 차량의 도착 구간, 상대적으로 뒤에서 출발한 차량의 출발 구간과 겹친다. 이 말은 즉슨 출발 구간이 앞선 순으로 정렬하면, 앞 구간 차량의 출발 구간은 더이상 다른 차량의 주행 구간과 겹치지 않아 단속 카메라의 범위를 줄일 수 있다는 것이다. 

 

구현 코드

코드에서 구현해야할 것은 두 가지다. ① 출발 구간이 앞선 순으로 정렬하기, ② 주행 구간이 겹치는 범위 찾기. 

 

Queue = [ ]

Routes = [ [-20, -15], [-18, -13], [-14, -5], [-5, -3] ]

먼저 단속 카메라를 달 범위를 저장할 큐를 생성한다. 왜 특정 위치가 아닌 범위를 저장하냐면, 범위의 어느 곳에라도 단속 카메라를 달아도 되니 겹치는 구간 찾기가 더 편리하기 때문이다. 큐를 생성했다면 출발 구간이 앞선 순으로 정렬해준다. 정렬의 기준은 routes[x][0]이 될 것이다.

 

Queue = [ [-20, -15] ]

Routes = [ [-18, -13], [-14, -5], [-5, -3] ]

첫 번째 차량의 범위를 구한다. 큐가 비어있으므로 겹치는 구간을 비교할 필요가 없으니, 바로 첫 번째 단속 카메라의 구간을 차량에 맞춰 [-20, -15]로 설정한다.

 

Queue = [ [-18, -15] ]

Routes = [ [-14, -5], [-5, -3] ]

queue[0] = [routes[1][0], min(queue[0][1], routes[1][1])]

두 번째 차량의 단속 카메라 범위를 구한다. 출발 위치가 더 뒤인 차량의 출발구간 (-18)과 도착이 더 이른 차량의 도착 구간(-15)이 기존 단속 카메라 설치 범위인 [-20, -15] 안이므로, 단속 카메라 설치 가능 범위를 좁혀 [-18, -15]로 설정한다. 도착 구간에서 작은 값을 찾는 이유는 출발 구간이 더 뒤라고 도착 구간도 더 뒤라는 보장이 없기 때문이다. (예: [ [1, 5], [2, 3] ]

 

Queue = [ [-18, -15], [-14, -5] ]

Routes = [ [-5, -3] ]

if routes[2][0] > max(queue[all][1])?
	queue.add(routes[2])

세 번째 차량의 주행 구간은 queue에 있는 단속 카메라 설치 가능 범위에 속하지 않는다. 이를 확인하는 방법은 세 번째 차량의 출발 구간이 설치 가능 범위의 도착 구간보다 큰 경우를 체크하면 된다. 그러므로 단속카메라 설치를 세 번째 차량의 주행 구간에 맞춰 하나 더 해야한다.

 

Queue = [ [-18, -15], [-5, -5] ]

Routes = [ ]

네 번째 차량을 단속할 카메라의 범위도 마찬가지로 구한다. [-18, -15]는 네 번째 차량을 단속할 수 있는 범위에 속하지 않으나, [-14, -5] 범위는 -5 구간이 겹치기 때문에 단속이 가능하다. 설치 가능 범위를 좁혀 [-5, -5] (사실상 반드시 -5 구간에 설치하라는 의미)를 큐에 저장하면 단속 카메라를 설치할 위치가 대략 정해진다.

 

result = queue.size

Queue를 보면 [-18, -5]처럼 달 수도 있고, [-17, -5], [-16, -5], [-15, -5]와 같이 달 수도 있다. 중요한 것은 단속 카메라의 정확한 위치가 아니라, 차량을 모두 단속할 수 있는 카메라의 최소 개수이다. queue의 크기는 곧 단속 카메라의 최소 개수가 된다.

 

정답 코드

1. C++

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {
    vector<vector<int>> cams;
    bool flag;
    sort(routes.begin(), routes.end(), [&](vector<int> a, vector<int> b)->bool {
        return a[0] < b[0];
    });
    
    for(auto& route : routes) {
        flag = false;
        for(int i = 0; i < cams.size(); i++) {
            if(route[0] <= cams[i][1]) {
                flag = true;
                cams[i][0] = route[0];
                cams[i][1] = min(route[1], cams[i][1]);
            }
        }
        if(!flag) {
            cams.push_back(route);
        }
    }
    
    return cams.size();
}

 

2. Python

def solution(routes):
    cams, flag = [], True
    
    for route in sorted(routes, key=lambda x:x[0]):
        flag = False
        for i in range(len(cams)):
            if route[0] <= cams[i][1]:
                flag = True
                cams[i][0],cams[i][1] = route[0], min(route[1], cams[i][1])
        if not flag:
            cams.append(route)
    
    return len(cams)