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

programmers.co.kr/learn/courses/30/lessons/42884

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

 간단하게 문제를 풀 수 있는 아이디어는 자동차를 빨리 진입한 순서대로 정렬하는데서 부터 시작한다. 그 후 첫 자동차와 두 번째 자동차가 공유하고 있는 도로를 업데이트하는 것이 문제풀이의 핵심이다. 

int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end());
    int answer = 1;
    // 공유하고 있는 도로의 시작 지점
    int common_begin = routes[0][0];
    // 공유하고 있는 도로의 끝 지점
    int common_end = routes[0][1];
    for(int i=1; i<routes.size(); ++i){
        // 이전 차와 도로를 공유하지 않으므로 CCTV를 늘려야한다.
        if(routes[i][0] > common_end){
            answer++;
            common_begin = routes[i][0];
            common_end = routes[i][1];
        // 다음차와 도로를 공유하고 있으므로 공유가 끝나는 지점에서 CCTV를 추가해주면 된다. 
        }else if( routes[i][1]<=common_end){
            common_begin = routes[i][0];
            common_end = routes[i][1];
        }
    }
    return answer;
}

이 코드에서 common_begin은 필요가 없다. 하지만 공유하고 있는 도로를 지속적으로 업데이트한다는 개념을 명시하려고 코드에 적어보았다. 줄어든 코드를 보면서 이해하기가 쉽지 않았다...

 

 CCTV의 개수가 1에서 시작함을 알고 있어야 한다. 마지막 공유 도로가 끝났을 때 CCTV를 늘려야 하지만 for loop는 더 이상 진행되지 않으므로 시작할 때 1을 늘려주면 된다.

 

---

 처음에 어떻게 풀어야 할 지 아이디어가 떠오르지 않아 2차원 배열을 사용하여 풀었다. 정확성 테스트는 통과했지만 효율성 테스트를 통과할리가 없었다. 그렇지만 내가 생각한 논리를 그대로 구현해서 뿌듯했다.

 다음은 2차 배열을 활용하여 무식하게 문제를 해결한 코드이다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

bool first(vector<int> a, vector<int> b){
    return a.at(0) < b.at(0);
}
bool second(vector<int> a, vector<int> b){
    return a.at(1) < b.at(1);
}

void print2D(vector<vector<int>>& dim2, vector<int>& sum){
    for(int i=0; i<dim2.size(); ++i){
        for(int j=0; j<dim2.at(i).size();++j){
            cout << dim2[i].at(j) << " ";
        } cout << "\n";
    } 
    for(int i=0; i<sum.size();++i){
        cout << sum[i] << " ";
    } cout << "sum\n\n";
    
}

void updates(int max, int max_idx, vector<vector<int>>& dim2, vector<int> &sum){
    for(int i=0; i<dim2.size(); ++i){
        if(dim2[i][max_idx]==1){
            for(int j=0; j<dim2[i].size(); ++j){
                dim2[i][j]=0;
            }
        }
    }
    sum = vector<int>(dim2.at(0).size(),0);
    for(int i=0; i<dim2.size();++i){
        for(int j=0; j<dim2[i].size(); ++j){
            if(dim2[i][j]==1) sum[j]++;
        }
    }
}

vector<int> getMax(vector<int> &sum){
    int max = 0;
    int max_idx = -1;
    for(int i=0; i<sum.size(); ++i){
        if(sum[i]>max){ 
            max = sum[i];
            max_idx=i;
        }
    }
    return {max, max_idx};
}

int solution(vector<vector<int>> routes) {

    sort(routes.begin(), routes.end(),second);    
    int end = (routes.end()-1)->at(1);

    sort(routes.begin(), routes.end(),first);    
    int begin = routes.begin()->at(0);

    vector<vector<int>> dim2(routes.size(), vector<int>(end-begin+1,0));
    
    vector<int> sum(end-begin+1,0);

    for(int d=0; d<routes.size(); ++d){
        int b = routes[d][0];
        int e = routes[d][1];
        for(int i=b-begin; i<e-begin+1; ++i){
            dim2.at(d).at(i)++;
            sum[i]++;
        }
    }
    int answer = 0;
    print2D(dim2,sum);
    while(getMax(sum).at(0)!=0){
        vector<int> max_idx = getMax(sum);
        int max = max_idx[0];
        int idx = max_idx[1];
        updates(max,idx,dim2,sum);

        print2D(dim2,sum);
        answer++;
    }

    return answer;
}

int main(){
    vector<vector<int>> routes = {{-20,15}, {-14,-5}, {-18,-13}, {-5,-3}};                // -> 2
    //vector<vector<int>> routes = {{-100,100},{50,170},{150,200},{-50,-10},{10,20},{30,40}}; // -> 4
    int result = solution(routes);
    cout << "result=" << result << endl;
}