https://programmers.co.kr/learn/courses/30/lessons/42884
처음 풀이를 생각했을 때는 3 가지 경우를 생각했었다.
범위 내에 감싸고 있을 경우, 최소 지점과 만날 경우, 최대 지점과 만날 경우
저런 식으로 3 가지 경우를 생각하여 코드를 구현하였는데 계속 틀렸었다.
생각해보니, 저런식으로 bound를 줄여나가면 예전에 줄였던 경우에서 커버가 가능한 경우가 있을 수 있었다(말이 굉장히 어색하고 어려운데, 어쨋든 Routes간의 순서에 따라 값이 달라져버리게 될 수 있었다는 뜻이다).
밑의 코드는 처음 생각했던 (틀린) 알고리즘..
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> routes) {
vector<pair<int,int>> bv; // bound_vector
// 범위 탐색
for(int i=0;i<routes.size();i++){
int start = routes[i][0], finish = routes[i][1];
bool stop = false, found = false; // 계속 진행 여부, 발견 여부
// bound_vector 내부에서 가능한지
for(int j=0;stop == false && j<bv.size();j++){
// CASE 1 감싸야 할 경우(내부 조정)
if(start >= bv[j].first && finish <= bv[j].second){
bv[j].first = start;
bv[j].second = finish;
stop = true, found = true; // for문 그만, 발견
}
// CASE 2 최소 만날 경우
else if(start <= bv[j].second && start >= bv[j].first){
bv[j].first = start;
stop = true, found = true; // for문 그만, 발견
}
// CASE 3 최대 만날 경우
else if(finish >= bv[j].first && finish <= bv[j].second ){
bv[j].second = finish;
stop = true, found = true; // for문 그만, 발견
}
}
// 발견 못했을 경우 추가
if(found == false){
bv.push_back(pair<int,int>(start, finish));
}
}
return bv.size();
}
그래서 데이터들을 시작점을 기준으로 먼저 정렬해야 했다!
정렬하고 bound를 끝점을 기준으로 잡고 다음 routes들과 비교하며 조정한다.
만약 줄여야하면 줄이고, 커버 가능하지 않다면 새로 cctv의 설치 범위를 지정한다.
이 때, greedy로 수행할 수 있던 이유는 처음 routes들을 정렬하고 접근하였기 때문이다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// v1,v2를 true를 기준으로 정렬
bool compare(vector<int> v1, vector<int> v2){
return (v1[0]<v2[0]);
}
int solution(vector<vector<int>> routes) {
int ans = 1;
sort(routes.begin(), routes.end(), compare); // 시작점 기준 정렬
int bound = routes[0][1]; // 첫 바운드(시작점 기준 정렬 상태이므로 바운드만 체크)
for(int i=0;i<routes.size();i++){
// 바운드 조정
if(bound >= routes[i][1])
bound = routes[i][1];
// 범위 내 존재 x
if(bound < routes[i][0]){
ans++; // 답 개수 증가
bound = routes[i][1];
}
}
return ans;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
프로그래머스_단어 변환 (2) | 2019.11.17 |
---|---|
프로그래머스_ 정수 삼각형 (0) | 2019.11.17 |
프로그래머스_타일 장식물 (0) | 2019.11.16 |
프로그래머스_N으로 표현 (0) | 2019.11.16 |
프로그래머스_2*n 타일링 (0) | 2019.11.16 |