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

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

프로그래머스

 

문제 설명

---

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

고속도로를 이동하는 차량의 경로 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

문제 풀이

---

정렬 + 그리디 문제.

차량의 진입이 빠른 순으로 정렬하면 다른 차량과의 이동 구간이 겹치는 구간 중 가장 큰 수에 카메라를 설치해야 하므로 카메라를 설치할 수 있는 최대 위치는 차량의 진출 지점이다. 이를 기록해놓는다.

만약 다음 차량의 진입 지점이 현재 설치할 수 있는 최대 위치보다 이전 또는 같다면 이동 구간이 겹치기 때문에 추가로 감시 카메라가 필요없고, 아니라면 감시 카메라가 추가로 필요하다. 이때  이동 구간이 겹친다면 다음 차량의 진출 지점을 확인해야 한다. 이전까지 설치할 수 있는 최대 위치보다 현재 차량의 진출 지점이 더 작다면 겹치는 구간 중 가장 큰 값은 현재 차량의 진출 지점이 되기 때문이다.

첫번째 차량에 대해서는 최대 -15까지 설치할 수 있지만 두번째 차량까지 고려한다면 두 차량의 겹치는 부분 중 가장 큰 -17에 카메라를 설치해야 한다.

 

cmp로 차량의 진입 지점이 작은 순, 같다면 진출 지점이 큰 순으로 정렬한 후, 첫번째 차량의 진출 지점을 기록해 놓는다. 이후 index 1부터 끝까지 설명한대로 탐색하며 이동 구간이 겹치지 않을 때 감시 카메라의 수를 증가시킨다. 이때 이 감시 카메라는 현재 차량과 이후 차량에 대한 감시 카메라가 아니라 이전 차량들에 대한 감시 카메라이기 때문에 맨 마지막 이동 구간에 대한 감시 카메라가 기록되지 않는다. 따라서 반복문을 빠져나간 후 1 증가시켜준다.

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

bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
    if (p1.first < p2.first)
    {
        return true;
    }
    else if (p1.first == p2.first)
    {
        return p1.second > p2.second;
    }
    else
    {
        return false;
    }
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    vector<pair<int, int>> v;
    for (int i=0;i<routes.size();i++)
    {
        v.push_back(make_pair(routes.at(i).at(0), routes.at(i).at(1)));
    }
    sort(v.begin(), v.end(), cmp);
    int currentEnd = v.at(0).second;
    for (int i = 1;i < v.size(); i++)
    {
        if (v.at(i).first <= currentEnd)
        {
            currentEnd = min(v.at(i).second, currentEnd);
        }
        else
        {
            currentEnd = v.at(i).second;
            answer++;
        }
    }
    answer++;
    return answer;
}