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

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

 

 

그리디 문제이다. 아이디어가 잘 떠오르지 않아서 어떻게 해야되는지 굉장히 어려웠다.

 

그리디 문제를 해결하는 방법이 있으면 좀 알아봐야겠다.

 

 

카메라를 최소화 해야 되기 때문에 범위가 최대한 겹치는 부분에 설치해야 하는 건 당연하다.

 

 

그리고 잘 생각해보면 어떤 두 범위가 포함 관계라면, 반드시 좁은 범위 안에다가 카메라를 설치해야한다.

하지만 지금 카메라가 설치되어 있는 구간을 벗어나는 경우에는 새로 카메라를 설치해 줘야 한다.

손으로 그린 겁니다. 발 아닙니다.

그럼 겹치는 경우는 어떤가

겹치는 경우에는 기존의 구간(빨깐 부분을)과 초록색과 겹치는 부분을 새로운 구간으로 잡고 거기에 카메라를 설치하면 된다. 이때도 카메라는 1개만 있으면 된다.

 

 

이렇게 범위를 벗어날 떄만 카메라 개수를 늘려주면 된다!!!

 

 

 

 

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

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b) {
    if(a[0] == b[0]) {
        return a[1] > b[1];
    }
    return a[0] < b[0];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    int cnt = 1;
    int low = routes[0][0];
    int high = routes[0][1];
    for(int i = 1; i < routes.size(); i++) {
        int left = routes[i][0];
        int right = routes[i][1];
        
        if(low <= left && right <= high) {
            low = left;
            high = right;
        } else if((left < low && left <= right) || (left <= high && high < right)) {
            low = max(low, left);
            high = min(high, right);
        } else {
            low = left;
            high = right;
            cnt++;
        }
    }
    
    answer = cnt;
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~