개요

프로그래머스 : 단속 카메라

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

  고속도로를 이동하는 차량의 경로 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
  입출력 예 설명

  -5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

  -15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
  

접근 방식

1. 한번씩 만난다라고 해서 굉장히 고민을 많이 한 문제이다.
   겹치는 부분을 어떻게 처리를 할지 모르겠던 문제다.

2. 검색해본 결과, 힌트를 얻었다. 생각만 잘 해내면 아주 쉬운 문제였다.

   차의 진출지점 기준으로 벡터를 정렬 후, 진출지점마다 카메라를 설치하는 것이다.
   다른 차의 범위를 조사할때 해당 범위에 카메라가 있는지만 조사하면 된다.
   조사할 때 다른차의 진입지점보다 큰 카메라가 있는지 조사하면된다.

   어차피 진출지점 기준으로 정렬되었으므로 다른 차의 진출지점은 무조건 이미 설치된 카메라보다 크기 때문이다.

3. 카메라 설치는 set을 이용했다.

전체 코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    bool isCameraInRange=false;
    set<int> cameraSet;
    sort(routes.begin(), routes.end(), [](const vector<int>& a, const vector<int>& b){return a.back()<b.back();});
    for(auto elem : routes){
        isCameraInRange=false;
        for(auto setElem : cameraSet){
            //카메라가 현재 차량의 진입/진출지점 사이에 있다면 패스 
            //진출지점기준으로 정렬되었으므로 카메라보다 진출지점이 무조건 크다.
            //따라서 카메라 위치가 진출지점보다 뒤인지만 조사하면된다.
            if(setElem>= elem.front()){
                isCameraInRange=true;
                break;
            }
        }
        if(!isCameraInRange)
        cameraSet.insert(elem.back());
    }
    
    return answer=cameraSet.size();
}

생각

다른 분의 풀이

이것과 유사하지만 set을 사용하지 않아도된다.
어차피 진출지점 기준으로 정렬이 되어있기 때문이다.

카메라도 마찬가지로 정렬이 된 상태이므로 마지막 카메라가 제일 위치가 떨어져있으므로
마지막 카메라와 현재 차의 진입 지점만 비교하면된다.

간결한 코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0, lastCamera= - 30'001;
    sort(routes.begin(), routes.end(), [](const vector<int>& a, const vector<int>& b){return a.back()<b.back();});
    for(auto elem : routes){
            //카메라가 현재 차량의 진입/진출지점 사이에 있다면 패스 
        if(lastCamera>= elem.front()) continue;
        lastCamera= elem.back();
        answer++;
    }
    
    return answer;
}