Programers 단속카메라 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

 

아이디어

prefix sum이 아닐까하는 생각으로 많이 고민을 했었는데 방법을 찾는 문제였습니다.

나가는 지점 순으로 정렬을 한 후 cameraPoint를 최소값인 -30000보다 아래로 잡고 설치된 지점보다 앞쪽에 위치한 진입점를 만날경우 해당 routes의 나가는 지점으로 변경 후 카메라의 개수를 늘려주는 조건으로 정렬된 routes를 순회하면 됩니다. 코드가 단순할수록 아이디어를 많이 필요로 하게되는 것이 느껴집니다.

 

 

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

using namespace std;

int solution(vector<vector<int>> routes) {
	int answer = 0;
	int cameraPoint = -30001;
	sort(routes.begin(), routes.end(),
		[](vector<int> a, vector<int> b)->bool {
		return a[1] < b[1];
	});
	for (auto &iter : routes) {
		if (cameraPoint < iter[0]) {
			answer++;
			cameraPoint = iter[1];
		}
	}

	return answer;
}