매우 오랜만에 적는 알고리즘 포스팅이다~!
요즘 아주 스스로가 맘에 안들어 죽겠다,,
6,7,8월 정신 차리고 준비 해야 하는데,, 라고 생각만 하고 정작 제대로 안함
집에 있다보니까 역시 집중이 잘 안되서 그런 것 같은데 그러면서 나오지도 않음
no answer.
이제야 몸을 움직여서 집 앞 카페에 와서 평균 3시간 걸리던 알고리즘 풀이를 1시간 만에 해결했다ㅋㅋㅋㅋㅋㅋ 진짜 비효율 최고다,,
주저리도 그만하고 프로그래머스 greedy 의 마지막 문제 단속 카메라를 복습해보자!
프로그래머스 단속카메라 (Greedy)
제한 사항 및 입출력
나의 풀이
고속도로로 들어오고 나가는 모든 차량이 최소한 한번씩 카메라에 잡힐 수 있도록 최소한으로 필요한 카메라 수를 구하는 문제이다
처음에 이리저리 고민하다 차량들을 진입 지점 기준으로 정렬하고 진출 지점으로 정렬하여 두 배열을 다루면서 접근하였는데 올바른 알고리즘인 듯 했지만 예외 경우를 생각해보다가 문제점을 발견하였다
4대의 차량이 위의 표처럼 들어오고 나가는 경우라면 routes는 이렇게 주어질 것이다
routes = [[0,2], [2,5], [5,7], [7,12]]
차량을 진입시점 기준으로 정렬하면, byEntery = [[0,2], [2,5], [5,7], [7,12]]
진출시점 기준으로 정렬 하면, byExit = [[0,2], [2,5], [5,7], [7,12]]
이 경우엔 정렬 전후가 같다
이 때 나의 알고리즘 대로라면,
byExit의 첫번째 차량의 진출 시점 = 2 를 기준으로 하여, byEntry 배열에서 진입 지점이 2 보다 작거나 같은 차량들은 모두 체크 되었다고 해서 패스 한다. 즉 A, B 차량은 카메라에 체크가 된 것이다!
이제 byExit 에서 다음 진출 시점을 보면 5 이다. 이때 5를 기준으로 해서 다시 byEnter의 진입 지점을 확인해 보면, [5,7] 이라는 어린 희생양이 기다린다,,!
이런식이라면 카메라는 총 3가지 지점에 설치될 것이다, 2/5/7 지점에!
맞나..? 아니다!!!!!
A, B는 2시점에, C,D 는 7 지점에서 확인되면 2대의 카메라만이 설치되면 해결되는데, 어찌 이런일이 발생했을까?!
맞다, 우리는 이미 확인 대상에서 제외된 차량 B의 진출 지점인 5를 기준으로 하였기 때문이다!
차량의 진입 진출 시점을 기준으로 하여 두가지의 배열 byEntry, byExit으로 차량들을 관리하다보니 이미 확인된 차량을 제외하지 않는, 쉽게말해 두 배열의 동기화가 이루어지지 않은 것이다!!!
차량의 진출 진입 시점들은 한 배열 안에서 관리 해야 한다는 것을 깨닫고 한 포스팅을 살짝 참고하여 다시 설계해 해결하였다
통과된 풀이
#include <vector>
#include <algorithm>
// 프로그래머스 Greedy - 단속카메라
using namespace std;
bool byExit(vector<int> route1, vector<int> route2) {
return route1[1] < route2[1];
}
int solution(vector<vector<int>> routes) {
int cameraAt = -30001;
vector<int> cameraLocation;
vector<vector<int>> routeByExit;
sort(routes.begin(), routes.end(), byExit);
routeByExit = routes;
for (int i = 0; i < routeByExit.size() ; ++i) {
if (routeByExit[i][0] > cameraAt){
cameraAt = routeByExit[i][1];
cameraLocation.push_back(cameraAt);
}else{
continue;
}
}
return cameraLocation.size();
}기본적으로 진출 시점을 기준으로 하여 차량들을 탐색한다
기존의 camera 지점보다 진입 지점이 작거나 같은 차량이라면 기존 카메라에 배당하고, 기존의 camera 지점보다 이후에 진입한 차량이라면 해당 차량의 진출 시점으로 새롭게 camera 위치를 변경해 탐색을 반복하는 간단한 방식이다
차량의 진입 시점은 -30,000 부터여서 기본 카메라 위치는 -30,001로 초기화 하였다.
풀고나니 그리 어렵지 않은 문제인데 왜 이상하게 두개의 배열을 만들어 난리를 쳤을까,, 싶다 ㅜ
6월안에 30 문제 solve 가 목표인데,,! 일단 이번주 10개 해결 가본드아!
