[PROGRAMMERS] Level 3 단속카메라(구현, 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 이하입니다.

입출력 예

routesreturn

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

2

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

📢 풀이

이 문제는 단순 구현문제로 규칙성만 찾는다면 매우 쉽게 풀리는 문제이다. 예제들을 그림을 통해 그려보면

 이런식으로 현재 겹치는 구간이 3개가 된다. 그런데 해당 문제는 최소 값을 물어보고 있으므로 가운데 빨간색을 제외한 2개가 정답이 되는 것이다.

겹치는 구간은 찾기가 쉽다. 그러나 중복 값을 어떻게 제거를 해야할까??

 

필자는 다음과 같은 방법으로 문제를 해결했다.

1. end 지점(고속도로 나가는 지점)을 기준으로 오름차순

2. for문을 활용해서 겹치는 구간을 전부 탐색

3. 더 이상 겹치지 않는 열부터 다시 탐색

 

즉, 3번의 과정을 통해 중복 값을 없애줄 수 있다. 이러한 로직이 가능한 이유는 1번에서 정렬을 해주었기 때문이다.

#include <vector>
#include <algorithm>
using namespace std;

bool compare(vector<int> v1, vector<int> v2) {
    return v1[1] < v2[1];
}
int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(), routes.end(), compare);
    int start = 0;
    for (int i = 0; i < routes.size(); i++) {
        if (start==i || routes[start][1] >= routes[i][0]) continue;
        else {
            answer++;
            start = i;
        }
    }
    return answer;
}

 

결과는 ....

📢 결론

오늘은 레벨3의 문제를 풀어보았다. 100등 안까지 쭈욱 달려봐야겠다.