[Algorithm] 프로그래머스 단속카메라 - C++, 그리디

코딩테스트 연습 - 단속카메라

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

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

    // sort
    sort(routes.begin(), routes.end());

    // solve
    int prev = routes[0][1];
    for(unsigned i = 1; i < routes.size(); i++){
        if(prev < routes[i][0]){
            prev = routes[i][1];
            answer++;
        }
        if(prev > routes[i][1])
            prev = routes[i][1];
    }

    return answer;
}

---

 그리디 문제 중에서 자주 나오는 유형이 아닐까 합니다. 일단 크게 3가지 상황이 있는데

 

- 다음 자동차가 나보다 느리게 나감

- 다음 자동차가 이전 자동차보다 먼저 나감

- 다음 자동차가 이전 차량이 나간 뒤 들어옴

 

 일단 느리게 나가는 경우는 생각해볼 필요가 없습니다. 수직선 상에서 겹치는 부분이있어 카메라 댓수를 늘릴 조건이 안됩니다. 부분집합처럼 포함되는 경우도 카메라의 수를 늘리는 조건이 안되지만 끝나는 시간 (prev)를 조절하는 조건이 됩니다.

 이는 예시로 첫 차가 0 ~ 100의 구간을 지나고 다음 차량이 10~20, 30~40을 각각 지난다고 하면 prev = 100 인 상태에서는 카메라를 1개면 충분하다고 인식하기 때문입니다. 그래서 카메라 수는 올리지 않되 prev = 20 으로 변경해 다음에 들어올 차량을 고려하자는 의미입니다.

 마지막 조건은 그냥 카메라를 추가로 설치해 주면 됩니다.

---

추가적으로 봐야할게 2개 정도 있습니다.

1. answer = 1 로 초기화

 차량이 들어오는 순간 무조건 카메라는 1대 필요하게 됩니다. 그러니 answer = 0 으로 되어있다는 점을 주의합시다.

 

2. 배열 저 상태로 정렬이 가능하다

    // make input
    for(unsigned i = 0; i < routes.size(); i++){
        cars[i] = make_pair(routes[i][0], routes[i][1]);
    }

    // sort
    sort(cars.begin(), cars.end());

 처음 문제 풀이를 할때 제 코드인데 알고보니 새 배열을 만들 필요 없이 맨 위 코드처럼 그대로 정렬해도 원하는 결과물이 나옵니다. 

추가 배열을 통해 제출한 코드

추가 배열 없이 만든 코드

 효율성에서 약간 차이가 나기도 하고 코드가 굳이 길어지기 때문에 그냥 그대로 정렬하는걸 추천드립니다...