프로그래머스 문제 풀이 단속카메라

문제 URL 단속카메라

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 입력입니다.

 

입력 :
routes = [ [-20, 15], [-14, -5], [-18, -13], [-5, -3] ]

 

이 경우 0번부터 3번까지의 차량을 그림으로 나타내면, 다음과 같습니다.

 

 

이 때, -5 지점에 카메라를 설치하면, 1번, 3번 차량을 감시할 수 있습니다.

 

 

이제 -15 지점에 카메라를 세우면 0번, 2번 차량을 감시할 수 있습니다.

 

 

뭐 문제에서는, -15라고 했지만, 사실 0번과 2번만 겹쳐있는 -18부터 -13 중 어느 곳에 설치하더라도 괜찮습니다. 이렇게 해서 최소 2대의 카메라로 모든 차량을 감시할 수 있습니다.

 

어떻게 문제를 해결할 수 있을까요? 제가 세운 방법은 "차량 동선이 최대한 많이 겹치는 구간에 카메라를 설치하자"입니다.

 

먼저 routes를 나간 지점 기준으로 정렬합니다.

 

# 나간 지점 기준 (route[1]) 으로 정렬
routes = [[-18, -13], [-14, -5], [-5, -3], [-20, 15]]

 

여기서, 정렬된 routes에서 첫 원소의 나간 지점에 카메라를 설치합니다.

 

routes = [[-18, -13], [-14, -5], [-5, -3], [-20, 15]]
prev_camera = -13 # 현재 설치된 카메라 위치
answer = 1 # 카메라 개수

 

그림으로 표현하면 다음과 같습니다.

 

 

이렇게 되면, 총 3대의 차량이 감시 카메라에 잡히게 됩니다. 다음과 같이 말이죠.

 

# 걸린 차량
[-18, -13] [-14, -5] [-20, 15]

 

이제 routes에서, 현재 카메라의 위치에서 잡히지 않은 차량을 찾아야 합니다. 여기서 잡히지 않은 차량이란, 들어온 지점이 prev_camera보다 오른쪽에 있는 경우를 뜻합니다.

 

즉, routes를 순회하면서 다음 수식을 만족하는 차량을 찾습니다.

 

prev_camera < route[0]

 

결론적으로 [-5, -3] 구간을 지나는 차량이 감시 카메라에 잡히지 않습니다. 따라서 카메라를 이 구간의 끝에 설치해줍니다.

 

routes = [[-18, -13], [-14, -5], [-5, -3], [-20, 15]]
prev_camera = -3 # 현재 설치된 카메라 위치
answer = 2 # 카메라 개수

 

그림으로 표현하면 다음과 같습니다.

 

 

-3에 카메라를 설치하면, 2개의 카메라로 모든 차량을 감시할 수 있게 됩니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. routes를 차량이 나간 지점(route[1]) 기준으로 정렬합니다.
2. routes를 순회합니다.
   1. 만약 prev_camera < route[0] 라면, 개수를 세고, prev_camera 위치를 route[1]로 합니다.
3. 개수를 반환합니다.

이 때 중요한 것은 문제에 나타났듯이 prev_camera를 -30000으로 먼저 초기화해줘야 한다는 점입니다. 다음을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다.

 

PYTHON 코드

def solution(routes):
    # 1. route[1] 기준으로 정렬
    routes = sorted(routes, key=lambda route: route[1])
    # 2. -30000부터 카메라 위치를 찾습니다.
    prev_camera = -30000
    answer = 0

    # 3. routes를 순회합니다.
    for route in routes:
        # 1. 만약 최근 카메라가 route[0]보다 작은지 체크합니다.
        # 1-1. 작다면, 카메라를 한 개 더 세웁니다.
        # 1-2. 최근 카메라의 위치를 갱신합니다.
        if prev_camera < route[0]:
            answer += 1
            prev_camera = route[1]

    # 4. 카메라 개수를 반환합니다.
    return answer

 

다음은 CPP 코드입니다. 알고리즘은 동일합니다.

 

CPP 코드

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

using namespace std;

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

    int prev_camera = -30000;
    int answer = 0;

    for (const auto & route : routes) if (prev_camera < route[0]) {
        answer += 1;
        prev_camera = route[1];
    }

    return answer;
}