[프로그래머스/C++] 단속카메라 풀이 (greedy를 스마트하게)

문제 이해

---

문제 설명

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

고속도로를 이동하는 차량의 경로 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. [진입기준으로 정렬할 경우]
   • 처음 차량이 제일 마지막에 진출할 경우 진입점마다 카메라 설치는 비효율적이다. (진입 카메라 불가)
   • 진입기준 진출할 때마다 카메라를 설치할 경우 위의 경우가 반례가 된다. (진출 카메라 불가)
4. [진출기준으로 정렬할 경우]
   • 진입하는 차량의 시각보다 마지막으로 설치된 카메라의 진출점이 이후라면 모두 단속이 가능하다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std; 

int solution(vector<vector<int>> routes) {
    int answer = 1;

	//따로 함수만들기 아까워서 람다함수로 구현하였다.
    sort(routes.begin(), routes.end(),
         [&](vector<int> a, vector<int>b) {
             return a[1] < b[1];
         });
    
    int now = routes[0][1] ;
    for(auto r : routes)
        if(r[0] > now) {
            answer++ ;
            now = r[1] ;
            cout << now ;
        }
    
    return answer;
}

---

느낀점: 그리디는 진짜... 항상 아이디어가 어렵다

참조링크: https://school.programmers.co.kr/questions/27135

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

프로그래머스