[프로그래머스/C++] 단속카메라

프로그래머스

 

• 일단 정렬
• 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
• 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
• 진입 지점과 진출 지점을 갱신
• 진입 지점과 진출 지점이 같은 경우에는 갱신 X
• 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
• 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
• 이를 반복

2레벨에 디펜스 게임?이랑 비슷한 느낌으로 접근하면 됨

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

using namespace std;

// 일단 정렬
// 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
// 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
// 진입 지점과 진출 지점을 갱신
// 진입 지점과 진출 지점이 같은 경우에는 갱신 X
// 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
// 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
// 이를 반복

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