[고득점Kit][그리디] 단속 카메라 ⭐⭐⭐

[그리디] 단속 카메라

난이도 ⭐⭐⭐

문제

• [-13, -14] 지점에 카메라를 설치하면 첫 번째, 두 번째, 세 번째 차량이 카메라를 만난다.
• [-5, -3] 지점에 카메라를 설치하면 네 번째 차량이 카메라를 만난다. -5 지점이라면 세 번째 카메라도 같이 만남

풀이

풀이는 SoftVanilla 님 블로그를 참고하였다.

이 문제의 내 풀이는 통과하지 못했다. 자꾸 테스트 케이스 몇 개만 틀리더라.. 심지어 기존에 푼 내 풀이를 백업해두지 못 해 잃어버렸다. 겉 보기엔 쉬워보였지만 왠지 모르게 머리가 복잡해지고 동공 지진 나는 그런 문제였다. ㅠ ㅜ 해당 블로거 분의 글을 읽고 제대로 이해할 수 있었다.

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

using namespace std;

bool compare(vector<int> a, vector<int> b)
{
    return a[0] < b[0];
}

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

가능한한 많은 자동차가 공통적으로 지나가는 곳, 즉 최대한 자동차들이 겹치는 구간에 카메라를 설치해야 최소로 카메라를 설치할 수 있다. 공통된 구간에 속하는 자동차 수가 많아지다가 자동차 하나라도 구간을 빠져나가서 수가 줄어든다면 바로 이전까진 최대 구간이였던 것이므로 그 때 answer 를 증가시키면 된다.

sort(routes.begin(), routes.end(), compare);

먼저 더 앞선 구간을 지나는 자동차 순으로 정렬을 한다. 지나가는 순서대로, 가장 먼저 진입하는 자동차부터 살펴보기 위하여.

공통 구간 찾기

• 뒤에 있는 자동차의 출발점이 앞에 있는 자동차의 퇴장점 보다 더 앞서 나오면 두 자동차는 공통 구간을 가지는 셈이다.
  • 공통 구간을 가지는 또다른 조건인, 앞에 있는 자동차의 출발점이 뒤에 있는 자동차의 출발점보다 앞선다는 것은 자동차를 지나가는 순서대로 정렬했기 때문에 너무 당연해져서 안따져도 된다.

if (routes[i][0] <= end)  // else 
    end = min(end, routes[i][1]);

• end 현재까지의 공통 구간의 끝 지점
  • 현재까지의 공통 구간에 i번째 자동차도 포함된다면 if (routes[i][0] <= end) 코드에선 else
    • 공통 구간 업데이트 하기
      • end를 새롭게 업데이트 해야 한다. 기존의 end보다 routes[i][1] i 번째 자동차의 퇴장점이 더 짧다면 그걸로 en를 업데이트 한다.
      • 공통 구간의 끝구간을 새롭게 업데이트 해주는게 필요하다. 끝 구간으로 공통 되었는지를 확인해야 하기 때문에

if (routes[i][0] > end)
{
    answer++;
    end = routes[i][1];
}

현재 차량 기준 더 이상 공통 구간이 없을 때 카메라 수를 1 늘리고 현재 차량이 속한 구간을 새로운 공통 구간으로 갱신한다.

• i번째 자동차는 현재까지의 공통 구간에 전혀 속하지 않는다면
  • i번째 자동차의 출발점은 end를 초과함.
• answer를 증가시킨다. 카메라를 현재까지의 공통 구간에 두어야함! 현재 구간까지 최대한 자동차가 많이 겹치는 구간인 것이기 때문에
• 새로운 공통 구간 업데이트 하기
  • end를 새롭게 업데이트 한다. 전혀 새로운 공통 구간이 생기는 것이므로 공통 구간에 속하지 않았던 i번째 자동차의 퇴장점으로 새롭게 업데이트 한다.
  • begin은 업데이트 하지 않아도 된다. 정렬 덕에 begin이 routes[i][0]보다 커질 일은 없기 때문이다. begin이 자기 자신의 값을 유지할 일도 없다. 항상 routes[i][0]로 업데이트 한다. 그래서 공통 구간을 찾고 업데이트 하는데에 begin은 필요 없다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기