[DAY84] Algorithm : Speed Cameras

모든 차량이 최소 한 번은 단속카메라를 만나도록 하려면 최소 몇 대가 필요한지 구하는 문제다. 구간(Interval) 문제의 핵심은 정렬이다. 보통 '끝나는 지점'을 기준으로 정렬하지만, 발상을 전환하여 '시작 지점'을 기준으로 내림차순 정렬하면 코드가 훨씬 간결해진다.

---

❓ 문제 분석

• 목표: 모든 차량의 경로가 겹치는 지점들에 최소 개수의 카메라 설치하기.
• 제약 조건: 차량 대수는 최대 10,000대, 좌표 범위는 -30,000 ~ 30,000. $O(N^2)$보다는 $O(N \log N)$이 적합하다.
• 핵심 키워드: "최소 몇 대", "경로가 겹치는", "진입/진출".

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음엔 진출 지점을 기준으로 오름차순 정렬하려고 했다. (가장 빨리 나가는 차를 잡으려면 그 차가 나가기 전에 찍어야 하니까)
• 하지만 C++ sort는 기본적으로 첫 번째 원소(진입 지점)를 기준으로 정렬하므로, 비교 함수(cmp)를 따로 짜야 하는 번거로움이 있었다.

2. 최종 해결책 (Solution)

• 발상의 전환: 문제를 거꾸로 생각했다. "가장 늦게 들어온 차"부터 처리하면 어떨까?
• 알고리즘 흐름:
  1. routes를 진입 지점 기준 내림차순으로 정렬한다. (sort + rbegin)
  2. 가장 늦게 진입한 차부터 순서대로 확인한다.
  3. 현재 설치된 카메라(camera)가 이 차의 진출 지점보다 더 뒤에 있다면? (즉, 이 차가 카메라보다 먼저 나가버려서 안 찍힌다면)
  4. 새 카메라를 이 차의 진입 지점에 설치한다. (그리디: 최대한 앞쪽에 설치해야, 그보다 더 일찍 진입해서 길게 뻗어있는 다른 차들도 같이 찍을 수 있다.)

---

💻 코드 구현

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;

    // sort(첫번째 원소)를 이용해 내림차순 정렬
    sort(routes.rbegin(), routes.rend());

    // 범위 밖의 값으로 초기화
    int camera = 30001; 

    // 뒤에서부터 탐색하며 카메라 설치
    // 차량의 진출 지점이 카메라 위치보다 작으면 -> 진입 지점에 카메라 설치
    for (const auto& route : routes) {
        if (route[1] < camera) {
            camera = route[0];
            answer++;
        }
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 진출 지점 기준 오름차순 정렬을 구현하려면 cmp 함수를 만들어야 해서 코드가 길어진다.
• 해결: 내림차순 정렬을 이용하면 진입 지점 기준으로 늦게 들어온 차부터 볼 수 있다. 이렇게 하면 vector의 기본 정렬 순서를 그대로 이용할 수 있어 코드가 매우 짧아진다. 논리적으로는 "진출 기준 오름차순"과 동치다.

---

✅ 오늘의 회고

항목	내용
유형	Greedy (탐욕법), 스위핑(Sweeping)
체감 난이도	중 (정렬 기준 잡기가 핵심)
복잡도	시간: $O(N \log N)$ (정렬), 공간: $O(1)$
새로 배운 것	문제의 기준을 뒤집어서(내림차순) 생각하면 구현이 훨씬 쉬워질 수 있다.