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

 

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

 

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

프로그래머스

---

 

 

해결전

 

Greedy Algorithm 탐욕법

 

---

 

 

처음 시도한 코드

 

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

// 시작 지점을 기준으로 오름차순 정렬. 시작 지점이 같으면 끝 지점을 기준으로 오름차순 정렬.
bool Compare(vector<int>& v1, vector<int>& v2) {
    if (v1[0] < v2[0]) return true;
    if (v1[0] == v2[0] && v1[1] < v2[1]) return true;

    return false;
}

int solution(vector<vector<int>> routes) {
    int n = routes.size();
   
    sort(routes.begin(), routes.end(), Compare); // 시작 지점을 기준으로 정렬

    int answer = 1;  		 // 첫 번째 카메라를 설치
    int curr = routes[0][1]; // 현재 카메라의 설치 위치는 첫 번째 차량의 끝 지점
    int next_curr = 0;
    int i = 1; // 두 번째 차량부터 시작

    while (i < n)
    {
        if (routes[i][0] <= curr) { // 현재 카메라 범위 안에 있는 차량을 처리
            next_curr = max(next_curr, routes[i][1]);
        }
        else {  // 새로운 카메라를 설치해야 하는 경우
            next_curr = max(next_curr, routes[i][1]);
            curr = next_curr;
            answer++;
        }

        i++;
    }

    return answer;
}

int main() {
    cout << solution({ {-20, 15},{-14, -5},{-18, -13},{-5, -3} }) << "\n"; // 2
    return 0;
}

 

 

차량의 진입 지점을 기준으로 정렬하여 각 차량의 진출 지점을 잘못 처리하였다. 

아래의 테스트 케이스의  (-20, 15) 처럼 범위가 넓은게 주어지는 경우를 계산하지 못한다. 

---

 

 

정답 코드

 

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

// 차량 진출 지점을 기준으로 오름차순 정렬. 진출 지점이 같으면 진입 지점을 기준으로 오름차순 정렬.
bool Compare(vector<int>& v1, vector<int>& v2) {
    if (v1[1] < v2[1]) return true;
    if (v1[1] == v2[1] && v1[0] < v2[0]) return true;

    return false;
}

int solution(vector<vector<int>> routes) {
    int n = routes.size();

    sort(routes.begin(), routes.end(), Compare); // 진출 지점을 기준으로 정렬
    
    int answer = 1;  		  // 첫 번째 카메라를 설치
    int curr = routes[0][1];  // 현재 카메라의 설치 위치는 첫 번째 차량 진출 지점
    int i = 1;  			  // 두 번째 차량부터 시작 

    while (i < n)
    {
    	// 현재 카메라(=진출 지점) 밖에 있는 차량인 경우
        if (curr < routes[i][0]) { 
            curr = routes[i][1];
            answer++;
        }

        i++;
    }

    return answer;
}

int main() {
    cout << solution({ {-2, -1},{1, 2},{-3, 0} }) << "\n"; // 2
    cout << solution({ {0, 0} }) << "\n"; // 1
    cout << solution({ {0, 1},{0, 1},{1, 2} }) << "\n"; // 1
    cout << solution({ {0, 1},{2, 3},{4, 5}, {6, 7} }) << "\n"; // 4
    cout << solution({ {-20, -15},{-14, -5},{-18, -13},{-5, -3} }) << "\n"; // 2
    cout << solution({ {-20, 15},{-14, -5},{-18, -13},{-5, -3} }) << "\n"; // 2
    cout << solution({ {-20, 15},{-20, -15},{-14, -5},{-18, -13}, {-5, -3} }) << "\n"; // 2
    return 0;
}

 

 

카메라는 진출한 지점을 기준으로 계산해서 설치해야 한다. 

 

현재 카메라의 범위 밖에 있는 차량을 만나면 새로운 카메라를 설치한다. 

 

정리하면, 차량의 진출 지점을 기준으로 정렬하고, 현재 카메라 범위(=진출 지점) 밖에 있는 차량을 만날 때마다 새로운 카메라를 설치한다.

 

---