rogramers : 단속카메라 - C++
11671 단어 greedyPROGRAMERSlevel3PROGRAMERS
단속카메라
코드
#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 수)
Author And Source
이 문제에 관하여(rogramers : 단속카메라 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-단속카메라-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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 수)
Author And Source
이 문제에 관하여(rogramers : 단속카메라 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-단속카메라-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)