단속 카메라

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

 

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

 

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

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

---

문제 해설

문제 자체가 완전탐색형태로 도 풀 수 있는데 너무 복잡해지고, 시간을 초과해서 시간초과가 나타난다.

 

좀 꼼수를 부려야 하는데, 문제 유형의 규칙을 확인해보면 된다.

 

모든 차량은 들어온 지점과 나간 지점이 존재한다.

언제나 나간지점을 기준으로 체크하면된다

(그 외에 설치해도 확인은 가능하나, 나간지점이 가장 큰 위치에 설치하여도 똑같은 효과가 나타남)

 

즉, 카메라를 생각하면 늘 가능한 겹치는부분의 가장 큰 나간위치를 기준으로 카메라가 한개씩 증가한다고 생각하면 된다.

---

첫 번째 시도

#include <string>
#include <vector>
#include <list>

using namespace std;

bool Overlap(const vector<int>& a, const vector<int>& b) {
    return (max(a[0], b[0]) <= min(a[1], b[1]));
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    list<vector<int>> routes_L(routes.begin(), routes.end());
    
    while(routes_L.size() > 0)
    {
        vector<int> select(routes_L.front());
        routes_L.pop_front();
        answer++;
        
        for(auto def = routes_L.begin(); def != routes_L.end(); ) {
            if(Overlap(select, (*def)))
                def = routes_L.erase(def);
            else
                ++def;
        }
    }

    return answer;
}

실패

 

겹치는 여부를 확인하고, 겹치는 객체를 OVerlap기준으로 순환하면서, 전체순환중 겹치는 객체를 날리게 했다.

 

그랬더니, 그 모든 결과가 효율적으로 나타나지는 않는다는걸 알게됨.

가장 먼저 제거된 객체가 가장 효율적인 객체들이 아닐 수 있기 때문

---

두 번째 시도

#include <string>
#include <vector>
#include <list>
#include <map>


using namespace std;

bool Overlap(const vector<int>& a, const vector<int>& b) {
    return (max(a[0], b[0]) <= min(a[1], b[1]));
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    list<vector<int>> routes_L(routes.begin(), routes.end());

    while (routes_L.size() > 0)
    {
        answer++;
        map<int, vector<vector<int>>> line_search;
        for (auto& line_1 : routes_L) {
            vector<vector<int>> search;
            for (auto& line_2 : routes_L)
                if (Overlap(line_1, line_2)) 
                    search.push_back(line_2);
            line_search[search.size()] = search;

        }

        for (auto& def : line_search.rbegin()->second)
            routes_L.remove(def);

    }

    return answer;
}

실패

 

이번에는 map형태로 데이터를 정리하고, 가장 큰 객체값을 확인한다음에 해당하는 거리값을 전부 날려주는 형태로 함수를 구성했다.

 

그래도 실패했다.

겹치는경우가 가장 많은 수 를 기준으로 카메라를 묶어두어도, 이 결과가 가장 효율적이지 않을 수 있기 때문이다.

---

세 번쨰 시도

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

using namespace std;

bool sorttwo(const vector<int>& a, const vector<int>& b) {
    return (a[0] < b[0]);
}

int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end(), sorttwo);
    int answer = 0;
    int chack = 300001;
    
    for(auto& def : routes) {
        if(chack <= def[0]) {
            chack = def[1];
        }
        else {
            chack = def[0];
            answer++;
        }
    }
    return answer;
}

실패

 

전 실패과정에서 뭐가 부족한지 생각해보니까. 아주 간단한 규칙을 깨달았다.

 

가능한. 묶을수 있는 수 중에서 나간 위치값을 기준으로 카메라를 배치하면 된다.

물론, 그 전에 sort를 해주어야 함을 분명하다.

 

그러나, 이러한 객체갱신 여부를 실수했다.

---

네 번째 시도

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

using namespace std;

bool sorttwo(const vector<int>& a, const vector<int>& b) {
    return (a[1] < b[1]);
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int chack = -30001;
    sort(routes.begin(), routes.end(), sorttwo);

    for (auto& def : routes) {
        if (def[0] > chack) {
            answer++;
            chack = def[1];
        }
    }

    return answer;
}

성공

이번에는 좀더 쉽게 생각하기로 했다.

 

그냥, 정렬해버리고 나간차량 기준으로 들어온 차가 나간차보다 더 클경우, 해당차량의 나간위치 기준으로 정리해주면된다.