프로그래머스] C++ 탐욕법(Greedy) - 단속카매라(level 3)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

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

1. 문제

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

고속도로를 이동하는 차량의 경로 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 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

2. 조건

1. routes에는 자동차의 시작점과 끝점이 있습니다. 시작점이 -20이고 끝점이 15라 한다면,

-20 -19 -18 - 17 ... 13 14 15 의 범위를 이동한 것이 됩니다.

2. 단속 카메라를 설치해야 하는데 모든 차량에 카메라가 거치도록 하고 싶습니다.

3. 이때 카메라를 최소 몇개 설치해야 모든 차량이 카메라를 지나갈 수 있을까?

4. 차량의 진입/진출 지점에 카메라가 있어도 만난것으로 간주.

3. 풀이

시작점을 기준으로 내림차순을 정렬했습니다.

내림차순으로 정렬한 이유는 음수가 있기 때문에 편하게 개산하려고 했습니다.

해당 예제를 내림차순으로 정렬하면 다음과 같은 형태가 나오게 됩니다.

[-5, -3]

[-14, -5]

[-18, -13]

[-20, 15]

여기서 첫번째 차량의 시작점은 -5이고 도착점은 -3입니다.

즉, -5부터 시작하여 -4, -3을 거쳤다는 뜻이됩니다.

그럼 저희는 다음 차량이 -5를 거쳤는지 안거쳤는지 파악하면 됩니다.(순서대로)

왜 순서대로? 내림차순 정렬을 했으니깐.

-5를 거쳤는지 안거쳤는지 확인하는 것은 결국, 다음 차량의 목적지가 -5보다 크다는 뜻이 됩니다.

-5보다 크다면 다음 차량 목적지가 -5이상 즉,

-5, -4, -3, -2, -1, 0, 1, 2, 3.... 이상이 되야 한다는 뜻입니다.

혹시 [-2, 10] 일 경우를 걱정하시는 분들이 있으실까봐 말씀 드리자면....

내림차순으로 정렬해서 [-5, -3]보다 [-2, 10]부분이 먼저 실행됩니다.

그럼 겹치지 않는 부분은 반대로 생각하면 됩니다. -5보다 작은놈들이 왔을 때....

-6, -7, -8, -9, -10.... 말이죠.

그림으로 표시해보면 이런식으로 됩니다.

겹치지 않는 곳에 카메라를 설치해주면 되니깐 아래와 같은 코드가 완성이 됩니다.

4. 코드

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

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

    sort(routes.rbegin(), routes.rend());

    int answer = 0, flag = 30001;

    

    for(size_t i = 0; i < routes.size(); i++){

        if(flag > routes[i][1]){

            flag = routes[i][0];

            answer++;

        }

    }

    return answer;

}