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

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=cpp

프로그래머스

 

벌써 세번째 푸는데 잘 못푼 나 ..

 

이런 문제를 풀 때는 케이스를 몇 개 생각해볼 수 있다.

 

 

검은색 범위가 원래 있었던 것이고 파란색이 들어온 차의 범위라고 하자. 그리고 빨간색 점이 카메라의 위치라고 하자. 

 

위사진의 케이스들은 모두 새로운 카메라가 필요없다. 첫번째, 두번째 케이스는 원래 있었던 카메라의 위치 = 차가 나가는 지점을 바꿀 필요가 없다. 이미 커버하고 있기 때문이다.

 

그러나 세번째 케이스의 경우는 기존 검은색의 끝점이라면 파란색이 찍히기 전에 나가버리므로 위치를 조정해주어야한다. 

 

그래서 여기서 알 수 있는 것이 

 

if 기존카메라위치 < 지금 들어온 차의 시작점 : 카메라가 하나 더 필요
else : 카메라는 필요 없지만 만약 지금 카메라위치 보다 들어온 차의 나가는 점이 빠르면 카메라 위치 조정

 

이러한 규칙을 찾아낼 수 있다.

 

그리고 이 들어오는 차의 순서를 정렬하는 것도 중요하다. 만약 

 

'

이런 케이스가 있다면 초록색 위치에 카메라가 설치되어야 한다. 그러나 만약 검은색, 빨간색, 파란색 순서로 정렬된다면 위 로직에서는 각 차량의 끝점에 카메라가 설치될 것이다. 그러므로 시작점이 같다면 끝점이 먼 곳부터 들어오도록 해야 카메라 위치를 갱신해갈 수 있다. 

 

이것을 코드로 표현하면 다음과 같다.

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

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

int solution(vector<vector<int>> routes) {
    int answer = 1;
    
    sort(routes.begin(), routes.end(), comp);
    
    int standardEnd = routes[0][1];
    
    for(int i = 1; i < routes.size(); i++){
        int nowStart = routes[i][0];
        int nowEnd = routes[i][1];
        if(standardEnd < nowStart) {
            answer++;
            standardEnd = nowEnd;
        }else{
            if(standardEnd > nowEnd) standardEnd = nowEnd;
        }
    }
    
    return answer;
}

 

sort는 일정하게 들어오지 않기 때문에 필요하고 그림으로 그려가며 판단해보자.