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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 그리디, 정렬 
풀이 시간 : 20분 

문제 풀이 

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치할 때, 최소 몇 대의 카메라가 필요한지 구하여라.

 

문제의 입출력 예제가 매우 친절하게 설명해주고 있다.

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

해당 예제를 그림으로 나타내 확인해보면 다음과 같다.

-15 지점과 -5 지점에 카메라를 설치하면 최소 개수로 모든 조건을 만족한다.

해당 예제의 결과를 살펴보면, -15 지점에서 첫번째, 세번째 차량이 카메라를 만나고, -5 지점에서 두번째, 네번째 차량이 카메라를 만난다. 

자세히 확인해보면 우리는 차량이 고속도로를 빠져나가는 시간이 빠른 순서대로 먼저 카메라를 만나게 세팅해야 한다는 것을 확인할 수 있다. 

 

예제의 rotues 배열을 빠져나가는 경우가 빠른 순으로 정렬하게 되면 [1, 3, 2, 4] 차량 순으로 정렬이 이루어질 것이고, routes 배열을 순회하면서 현재 인덱스의 차량의 진입 위치가 이전 차량의 빠져나가는 위치보다 크다면, 이전 차량의 빠져나가는 위치를 임계값으로 잡은 뒤, 해당 임계값에 포함되는 나머지 차량들은 카메라에 찍혔다고 가정하는 것이다.

 

이를 구현하기 위해서 `deque`, 즉 덱을 사용하였다. rotues의 인덱스를 돌 때마다 덱의 front의 빠져나가는 값과 비교해주었고, 만약 현재 인덱스의 출발지 값이 덱의 front의 빠지는 값보다 커진다면, 덱의 front의 빠지는 값에 속하는 모든 차량을 pop시켜준 뒤 answer를 증가시켜 주었다.

 

이를 통해 시간복잡도 $O(차량의 대수(N)) + O(NlogN)$ 를 사용하여 문제를 해결할 수 있다.

 

코드

/*
모든 차량이 고속도로에서 단속용 카메라를 한 번은 만나도록 설치하고자 함
차량의 경로가 매개변수로 주어짐
최소 몇 대의 카메라를 설치해야 하는지 return

풀이 : 정렬, 그리디
지점이 끝나는 시점이 빠른 차량 순으로 정렬
지점이 끝나는 시점의 차량이 카메라를 만났는지 확인
-> 만약 안만났으면, 끝에 카메라 설치
새로 들어온 차량의 시작 위치와 마지막 차량의 끝나는 위치를 확인 
끝나는 지점에 카메라 설치 후 지점이 겹치는 차량은 다 빼기
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
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;
    
    // 0. 정렬
    sort(routes.begin(), routes.end(), cmp);
    
    deque<pair<int, int>> q;
    // 1. 순차 탐색
    q.push_back({routes[0][0], routes[0][1]});
    int camera = 0;
    for (int i=1;i<routes.size();i++){
        int start = routes[i][0], end = routes[i][1];
        if (!q.empty() && start > q.front().second){
            camera = q.front().second;
            while (!q.empty() && q.front().first <= camera && camera <= q.front().second)
                q.pop_front();
            answer++;
        }
        q.push_back({start, end});
    }
    if (!q.empty())
        answer++;
    
    return answer;
}

배운 점 

문제를 보고 빠르게 그리디 알고리즘과 정렬을 생각해냈다.

해당 문제를 통해 점점 그리디 알고리즘에 익숙해지고 있다는 것을 느꼈다. 모든 알고리즘을 문제없이 즉각적으로 생각해 낼 수 있을 때까지 열심히 해야겠다.
기분이 좋군 !