프로그래머스 - 단속카메라(C++)

 탐욕법으로 분류된 문제이지만 사실상 그냥 구현이라고 봐야할 것 같다.

우선 항상 이런 문제를 보면 정렬을 떠올려야한다. 결과는 같지만 차가 들어오는 순서에 따라 연산이 달라지기 때문이다.

 

먼저 이 문제는 들어오는 첫번째 들어오는 시간을 기준으로 오름차 정렬하고 푸는게 가장 편하다.

1. i번 차의 나가는 지점을 기준으로 정해둔다.

2. i+1번 차가 들어오는 지점이 현재 기준점보다 오른쪽이다. 즉 기준 카메라로 커버할 수 없으면 카메라를 한개 추가하고 현 i+1번 차의 시작점으로 기준을 다시 잡는다.

3. i+1 번 차가 나가는 지점이 기준점보다 왼쪽이거나 같다. 즉 기준 카메라로 커버할 수 있다. 그럼 카메라의 위치를 i+1번이 나가는 지점으로 바꾼다. 왜냐하면 카메라로 많은 차를 커버해야하기 때문이다.

 

그림을 그려서 파악하는 것이 가장 좋은 방법이다. 탐욕법도 코드를 엄청나게 쓰는 경우는 많이 없기 때문에 내 논리가 정말로 맞는지, 예외는 없는지 손으로 충분히 정리하고 들어가는 것이 중요하다. 

 

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

bool comp(vector<int> a, vector<int> b){
    return a[0] < b[0];
}

int solution(vector<vector<int>> routes) {
    int answer = 1;
    
    sort(routes.begin(), routes.end(), comp);
    
    vector<int> camera;
    int tmp;
    for(int i = 0; i < routes.size(); i++){
        if(i == 0){
            tmp = routes[i][1];
            continue;
        }
        if(routes[i][0] > tmp) {
            answer++;
            tmp = routes[i][1];
        }
        else if (routes[i][1] <= tmp){
            tmp = routes[i][1];
        }
    }
    
    return answer;
}