프로그래머스 단속카메라 c++ (탐욕법)

문제 출처 : https://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 이하입니다.

입출력 예

입출력 예 설명

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

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

 

풀이 

'프로그래머스 / 탐욕법(Greedy) / 단속카메라'로 분류되어 있는 문제이다.

 

우선 차가 진입하는 시간별로 오름차순 정렬을 하고,

현재 차가 나가는 시점을 temp에 저장한다.

temp보다 다음 차의 들어오는 시점이 크다면 카메라를 설치하고,

temp를 다음 차의 나가는 시점으로 갱신한다.

 

만약 다음 차가 현재 차가 나가기 전에 들어왔지만,
다음 차가 현재 차보다 빨리 나간다면 temp를 다음 차가 나가는 시점으로 갱신한다.

 

차가 나가는 시점으로 오름차순 정렬하거나, 차가 진입하는 시점을 내림차순으로 정렬할 시에는

한 개의 if문으로 풀 수 있으니 한 번 생각해 보기 바란다.

 

코드

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

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