프로그래머스 문제 - 단속카메라

프로그래머스 단속카메라 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

10000대 이하의 차량이 움직이는 경로가 주어집니다.
경로는 -30000이상 30000이하로 주어집니다.
움직이는 차량을 카메라로 전부 찍어야합니다.
최소한의 카메라를 사용하여 모든 차량을 찍어야합니다.

카메라를 어떻게 설치해야 하는지 생각해야 합니다.

문제 풀이

여러 경로를 지나는 차량들을 최소한의 카메라를 설치하여 모든 차량들을 찍어야됩니다.
예제를 그림으로 그려보면 이러한 모양이 나옵니다.

계산을 편하게 하기 위하여 정렬을 해보면 아래와 같은 그림이 나옵니다.

차량이 움직이는 범위 내에 카메라가 없다면 도착 지점에 카메라를 설치한 후 다음 차량을 확인합니다.
도착 지점을 기준으로 정렬을 하였기 때문에 차량의 출발 지점보다 카메라가 더 앞에 있다면 그 차량은 카메라에 찍힌다는 뜻입니다.

이런 식으로 모든 차량을 검색하면 됩니다.

전체 코드

이번 문제는 정렬을 잘 이용하면 풀 수 있는 문제였습니다.

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

using namespace std;

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

int solution(vector<vector<int>> routes) {
    int answer = 0;
    vector<int> camera;
    int cameraPoint;
    bool isCameraInstall;
    
    //도착지점을 기준으로 오름차순해줍니다
    sort(routes.begin(), routes.end(), compare);
        
    for(int i = 0; i < routes.size(); i++)
    {
    	//설치된 카메라들에 차량이 지나가는지 확인합니다.
        for(int temp : camera)
        {
            //카메라가 설치된 지점에 차량이 지나간다면 설치하지 않고 넘어갑니다
            if(temp >= routes[i][0] && temp <= routes[i][1] && !isCameraInstall)
            {
                isCameraInstall = true;
                break;
            }
        }
        //설치된 카메라에 차량이 지나가지 않는다면 도착 지점에 카메라를 설치합니다
        if(!isCameraInstall)
        {
            camera.push_back(routes[i][1]);
            answer++;
        }
        isCameraInstall = false;
    }
    
    return answer;
}

출저

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