단속카메라

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
// 1210 ~ 0103
using namespace std;
bool compare(vector<int> next, vector<int> cur){
    if(next[1] == cur[1]) return next[0] < cur[0]; // next가 cur보다 작으면 swap
    return next[1] < cur[1]; // next가 cur보다 작으면 swap
}
int solution(vector<vector<int>> routes) {
    vector<vector<int>> second_pos(routes.begin(), routes.end());
    vector<vector<int>> first_pos(routes.begin(), routes.end());
    sort(second_pos.begin(), second_pos.end(), compare);
    sort(first_pos.begin(), first_pos.end());
    map<pair<int,int>, bool> cctv;
    int ans=0;
    int idx=0;
    for(int i=0;i<second_pos.size();i++)
    {
        auto cur = second_pos[i];
        if(cctv[{cur[0],cur[1]}]) continue;
        // 하나의 경로가 끝날 때 마다 1대의 cctv수 만큼 증가해야 한다
        ans++;
        // 등호 주의! 범위가 겹칠 때 그곳에 cctv를 두면 두 곳 모두 해결됨
        while(first_pos[idx][0] <= cur[1]) 
        {
            auto a = first_pos[idx];
            cctv[{a[0],a[1]}] = true;
            idx++;
            if(idx == first_pos.size()) goto stop;
        }
    }
    stop:;
    return ans;
}

• 핵심 아이디어
  • 경로가 일찍 끝나는 것 부터 cctv를 설치하는데 동시에 포함되는 경로는 같은 cctv로 처리할 수 있음
    --> 경로가 끝나는 것을 기준으로 오름차순 정렬 + 경로의 시작이 빠른 것 순서대로 정렬 + idx 증가
  • map을 이용해서 이미 처리된 경로는 continue로 넘긴다

• 주의
  : 범위가 겹칠 때에 해당 위치에 cctv를 놓으면 걸친 곳 모두 하나의 cctv로 해결 가능
  --> while문 조건에 등호(=) 꼭 필요

• 느낀 점
  • 회의실 배정 / 강의실 배정 두 그리디 유형과 비슷한 듯 다르다!
    --> 회의실 배정 / 강의실 배정 / 최소 cctv설치 3가지 유형을 머리에 기억해두자
  • 회의실 배정 : 하나의 회의실이 있을 때 최대한 많은 수업을 듣도록 수업 배정
    --> 종료시간 정렬 + 단순 비교
  • 강의실 배정 : 모든 수업을 듣는데 필요한 최소 강의실 수 (겹치는 최대 수)
    --> 시작시간 정렬 + priority_queue 사용
  • cctv 설치 : 최소 하나의 경로에 하나의 cctv 설치 (최소 cctv 수)