단속카메라 C++(그리디, 탐욕법)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라 | 프로그래머스

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

문제!!

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다. 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

예시

routes	return
{{-20,15}, {-14, -5}, {-18, -13}, {-5, -3} }	2
{{-2, -1}, {1, 2}, {-3, 0} }	2
{ {0, 0} }	1
{ {0, 1}, {0, 1}, {1, 2} }	1
{{0, 1}, {2, 3}, {4, 5}, {6, 7} }	4
{{-20, 15}, {-14, -5}, {-18, -13}, {-5, -3} }	2
{ {-20, 15}, {-20, -15}, {-14, -5}, {-18, -13}, {-5, -3} }	2

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

---

2. 문제풀이

어떻게 보느냐에 따라서 어렵고도 쉬운 문제라고 생각합니다. 저는 풀때 별 생각없이 이렇게 하면 되겠구나 하고 풀었는데 블로그에 풀이를 적으려니까 생각보다 어렵네요.   1. 정렬을 합니다. 기준점은 차량이 진입하는 순간입니다. 정렬을 하는 이유는 순서대로 접근하기 쉽게하기 위해서입니다.   2. 처음 차가 나가는 거리를 임시변수에 넣어줍니다. 이 값을 이용해서 비교를 합니다.   3. 다음차가 현재차가 나간후에 들어온다면 카메라를 추가해야합니다. 나가는 순간에 카메라를 설치해도 다음차를 찍지못하기 때문입니다.   4. 현재차보다 다음차가 나가는 거리가 짧다면 변수값을 갱신해줍니다. 현재 차보다 늦게 들어왔지만 더 빨리 나가는 차가 있을때는 둘이 겹치는 부분에 카메라를 두기 위해서 입니다.   5. 위 과정을 반복하면 최종 카메라 -1개가 나옵니다. 마지막 카메라가 추가되지 않기 때문입니다. 따라서 시작할때 카메라 대수를 1대로 설정하거나 반환전에 +1을 해서 리턴합니다.

---

3. 소스코드

3.1 주석없는 코드

#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 (auto a : routes) {
        if (temp < a[0]) {
            answer++;
            temp = a[1];
        }
        if (temp >= a[1])    temp = a[1];
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<vector<int>> routes) {
    //기본 카메라 1대
    int answer = 1;
    //들어온 리스트 정렬
    sort(routes.begin(), routes.end());
    //비교를 위해 처음차가 나가는 부분 체크
    int temp = routes[0][1];
    //리스트 순회하기
    for (auto a : routes) {
        //현재 차가 나가는 부분보다 뒤에 차가 들어온다면
        if (temp < a[0]) {
            //카메라 설치
            answer++;
            //나가는 부분 정정
            temp = a[1];
        }
        //현재 차보다 뒤차가 먼저나가면 
        if (temp >= a[1])    temp = a[1];// 나가는 부분을 뒷차로 수정
    }
    return answer;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int solution(vector<vector<int>> routes) {
    //기본 카메라 1대
    int answer = 1;
    //들어온 리스트 정렬
    sort(routes.begin(), routes.end());
    //비교를 위해 처음차가 나가는 부분 체크
    int temp = routes[0][1];
    //리스트 순회하기
    for (auto a : routes) {
        //현재 차가 나가는 부분보다 뒤에 차가 들어온다면
        if (temp < a[0]) {
            //카메라 설치
            answer++;
            //나가는 부분 정정
            temp = a[1];
        }
        //현재 차보다 뒤차가 먼저나가면 
        if (temp >= a[1])    temp = a[1];// 나가는 부분을 뒷차로 수정
    }
    return answer;
}
 
void print(vector<vector<int>> routes, int answer){
    int t = solution(routes);
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
}
 
 
int main(){
    print({ {-20,15}, {-14, -5}, {-18, -13}, {-5, -3} }, 2);
    print({ {-2, -1}, {1, 2}, {-3, 0} }, 2);
    print({ {0, 0} }, 1);
    print({ {0, 1}, {0, 1}, {1, 2} }, 1);
    print({ {0, 1}, {2, 3}, {4, 5}, {6, 7} }, 4);
    print({ {-20, 15}, {-14, -5}, {-18, -13}, {-5, -3} }, 2);
    print({ {-20, 15}, {-20, -15}, {-14, -5}, {-18, -13}, {-5, -3} }, 2);
    return 0;
}

---

4. 결과