C++ 프로그래머스 단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

 

비슷한 문제를 본 적 있어서 그리디로 풀면 될 것 같다고 생각 했지만 틀린 문제..

했던 생각은 가장 많이 겹치는 것을 선택하면 되지 않을까 생각했는데, 이렇게 구현하면 완전탐색과 다름없이 최악의 경우 모든 경로의 모든 구간을 조사해야 한다.

정확도 테스트는 통과하지만 시간 초과가 발생하여 틀리게 된다.

 

처음 틀린 풀이

 

1. 진출 시간 순으로 정렬을 한다.

2. 앞의 경로에서부터 구간의 모든 점에 대해 모든 경로를 순회하며 겹치는 구간의 수를 센다.
3. 시작점이 어떤 한 점보다 앞에 있다면 카메라가 설치 될 수 있으므로, hasCamera를 true로 설정한다.

4. 카메라가 설치되지 않은 경로에 대해 반복한다.

 

위 풀이는 너무 많은 연산을 수행하고 있다.

#include <string>
#include <vector>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

bool comparator(const vector<int> &a, const vector<int> &b) {
    return a[1] < b[1];  // Compare by second element
}

bool hasCamera[10001];

int solution(vector<vector<int>> routes) {
    int answer = 0;
    // greedy: 최대한 많이 겹치는 곳에 설치하되 숫자가 같은 경우 뒤에 추가
    // 1. 이동경로를 진출 시간 순으로 정렬
    // 2. 자동차의 이동 경로를 진입 시간에서부터 진출 시간까지 겹치는 부분이 가장 많은 곳에 추가
    // 2-1. 만약 겹치는 구간이 같으면 뒤에 추가
    
    sort(routes.begin(), routes.end(), comparator);
    int lastPos;
    // [[-20, -15], [-18, -13], ...]
    // -20보다 작거나 같은 것의 개수 ~ -15보다 작거나 같은 것의 개수
    for(int i=0; i<routes.size(); i++) {
        if(hasCamera[i])    continue;
        hasCamera[i] = true;
        answer++;
        int st = routes[i][0];
        int en = routes[i][1];
        int mxPos = st;
        int mxCnt = 1;
        for(int pos=st; pos<=en; pos++) {
            int cnt = 0;
            for(int k=i+1; k<routes.size(); k++) {
                if(routes[k][0] <= pos) {
                    cnt++;
                    hasCamera[k] = true;
                }
            }
            if(cnt >= mxCnt) {
                mxCnt = cnt;
                mxPos = pos;
            }
        }
    }
    return answer;
}

 

대략 상한을 구하면 O(10000*60000*10000) = O(6^12)으로 시간 내에 연산을 마칠 수 없다.

 

고친 풀이

진출 시간을 기준으로 정렬한 것을 더 활용해야 된다고 생각하였다.

첫 번째 경로의 진출 시간에 카메라를 추가하고, 이후 아래 조건에 따라 구분하여 수행하였다.

1. 만약 i번 째 경로의 진출 시간보다 i+1번 째 경로의 진입 시간이 작다면 자동으로 i+1번 째 경로도 카메라가 설치된다.

=> pass

 

2. 만약 i번 째 경로의 진출 시간보다 i+1번 째 경로의 진입 시간이 더 크다면 i+1번 째 경로는 카메라가 설치되지 않는다. 

=> 카메라를 i+1번째 경로의 진출 지점에 설치하고 마지막 카메라가 설치된 지점을 갱신한다.

 

왜 진출 지점에 설치하는가?

진출 시간을 기준으로 정렬하였으므로, 뒤의 경로의 진출 시간은 항상 앞의 경로보다 같거나 크게 된다. 

따라서 뒤의 경로는 진입 지점만 고려해주면 되는데, 설치하는 지점을 최대한 크게 하는 것이 뒤에 있는 경로의 진입 지점보다 클 가능성이 커진다. 즉, 더 많은 수의 경로와 겹칠 가능성이 크다.

 

위 규칙을 적용하여 코드를 작성하면 다음과 같다. 

#include <string>
#include <vector>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

bool comparator(const vector<int> &a, const vector<int> &b) {
    return a[1] < b[1];  // Compare by second element
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    sort(routes.begin(), routes.end(), comparator);
    
    int pos = -30001;
    for(int i=0; i<routes.size(); i++) {
        if(routes[i][0] > pos) {
            answer++;
            pos = routes[i][1];
        }
    }

    return answer;
}

정렬에 의해 시간 복잡도가 좌우되므로 O(nlogn)에 풀이가 가능하다.