[PG] 단속카메라 [C++]

 

프로그래머스

 

백준에서 정렬, 스위핑 태그가 붙어있는 문제들의 풀이 유형이 떠올라 바로 적용했다.

 

우선 나가는 지점 오름차순으로 정렬한다.

(나가는 지점이 같다면, 들어오는 지점이 작은 것이 앞으로 오도록 한다.)

 

입출력 예

 

정렬하면 이렇게 된다

 

최대한 많은 차량의 경로가 겹쳐야 단속카메라를 적게 달 수 있다.

나가는 지점을 기준으로 정렬했으니,

앞 차량의 나가는 지점(기준)이 뒷 차량의 들어가는 지점보다 크거나 같은 경우 차량들의 경로가 겹치므로

언제까지 겹치는지 확인하고 겹치지 않는 순간 단속카메라를 설치하고 기준을 바꿔준다.

 

첫 차량(i = 0)의 나가는 지점을 기준으로 잡고, routes를 순회해 보자. (기준 : -15)

i = 1, 차량의 들어오는 지점(-18)이 기준보다 작으니 Pass

i = 2, 차량의 들어오는 지점(-14)이 기준보다 크다. 기준인 -15 위치에 단속카메라를 설치(answer++)하고, 기준을 현재 차량이 나가는 -5로 바꿔주자.

i = 3, 차량의 들어오는 지점(-5)이 기준과 같으니 Pass

 

순회가 끝났고, 마지막 i가 2, 3인 차량이 찍히는 단속카메라를 설치하지 않았으니 설치(answer++)하자.

 

 

** 다른 사람의 코드를 보니 시작 기준점을 진입/진출 지점의 최솟값보다 작은 -30,001로 잡고 0번째 차량부터 검사하면, 순회가 끝난 후 answer++를 해줄 필요가 없다.

 

코드

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    sort(routes.begin(), routes.end(), [&](vector<int> a, vector<int> b) {
       if (a[1] == b[1]) {
           return a[0] < b[0];
       } else {
           return a[1] < b[1];
       }
    });
    
    int pivot = routes[0][1];
    for (int i = 1; i < routes.size(); i++) {
        if (routes[i][0] > pivot) {
            answer++;
            pivot = routes[i][1];
        }
    }
    answer++;
    return answer;
}