프로그래머스_단속카메라

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

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

처음 풀이를 생각했을 때는 3 가지 경우를 생각했었다.

범위 내에 감싸고 있을 경우, 최소 지점과 만날 경우, 최대 지점과 만날 경우

저런 식으로 3 가지 경우를 생각하여 코드를 구현하였는데 계속 틀렸었다.

생각해보니, 저런식으로 bound를 줄여나가면 예전에 줄였던 경우에서 커버가 가능한 경우가 있을 수 있었다(말이 굉장히 어색하고 어려운데, 어쨋든 Routes간의 순서에 따라 값이 달라져버리게 될 수 있었다는 뜻이다).

밑의 코드는 처음 생각했던 (틀린) 알고리즘..

#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> routes) {
    vector<pair<int,int>> bv; // bound_vector
    
    // 범위 탐색
    for(int i=0;i<routes.size();i++){
        int start = routes[i][0], finish = routes[i][1];
        bool stop = false, found = false; // 계속 진행 여부, 발견 여부
        
        // bound_vector 내부에서 가능한지
        for(int j=0;stop == false && j<bv.size();j++){
            // CASE 1 감싸야 할 경우(내부 조정)
            if(start >= bv[j].first && finish <= bv[j].second){
                bv[j].first = start;
                bv[j].second = finish;
                stop = true, found = true; // for문 그만, 발견
            }
                
            // CASE 2 최소 만날 경우
            else if(start <= bv[j].second && start >= bv[j].first){
                bv[j].first = start;
                stop = true, found = true; // for문 그만, 발견
            }
            
            // CASE 3 최대 만날 경우
            else if(finish >= bv[j].first && finish <= bv[j].second ){
                bv[j].second = finish;
                stop = true, found = true; // for문 그만, 발견
            }
        }
        
        // 발견 못했을 경우 추가
        if(found == false){
            bv.push_back(pair<int,int>(start, finish));
        }
    }    
    return bv.size();
}

그래서 데이터들을 시작점을 기준으로 먼저 정렬해야 했다!

정렬하고 bound를 끝점을 기준으로 잡고 다음 routes들과 비교하며 조정한다.

만약 줄여야하면 줄이고, 커버 가능하지 않다면 새로 cctv의 설치 범위를 지정한다.

이 때, greedy로 수행할 수 있던 이유는 처음 routes들을 정렬하고 접근하였기 때문이다.

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

// v1,v2를 true를 기준으로 정렬
bool compare(vector<int> v1, vector<int> v2){
    return (v1[0]<v2[0]);
}

int solution(vector<vector<int>> routes) {
    int ans = 1;
    sort(routes.begin(), routes.end(), compare); // 시작점 기준 정렬
    int bound = routes[0][1]; // 첫 바운드(시작점 기준 정렬 상태이므로 바운드만 체크)
    for(int i=0;i<routes.size();i++){
        // 바운드 조정
        if(bound >= routes[i][1]) 
            bound = routes[i][1];
        
        // 범위 내 존재 x
        if(bound < routes[i][0]){
            ans++; // 답 개수 증가
            bound = routes[i][1];   
        }
    }
    return ans;
}