(C++) - 프로그래머스(Programmers) : 징검다리 답

https://programmers.co.kr/learn/courses/30/lessons/43236?language=cpp

코딩테스트 연습 - 징검다리

이분탐색 문제였습니다.

 

풀이방법

바위 사이의 거리를 mid로 생각해 해당 조건을 찾았을 때의 거리들의 max값을 찾는 이분탐색을 시행하였습니다.

 

 1. mid보다 바위 사이의 거리가 작다면 제거해준다. removeCount값을 증가시킵니다.

 

 2. 모든 바위를 제거했을때의 removeCount값이 n보다 크면 너무 많이 지웠으므로 지우는 거리에 기준이 되는 거리값을 줄여줍니다.

 

 3. 모든 바위를 제거했을때의 removeCount값이 n보다 작거나 같을때 answer를 갱신 그리고 거리를 늘려줍니다.

 

Code

#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    //바위를 없앨 거리를 이분탐색으로 돌린다.
    int l = 0;
    int r = distance;
 
    while(l<=r){
        int mid = (l+r)/2; //바위 사이의 거리들 중 최대값을 찾는다.
        int removeIdx = -1;
        int removeCount = 0;
        for(int i = 0 ; i<=rocks.size(); i++){
            // int d = i==0? rocks[i]:
            // i==rocks.size() ? distance - rocks[rocks.size()-1] : rocks[i]-rocks[removeIdx];
            int d;
            if(i==0){ //돌의 처음
                d = rocks[i];
            }else{
                //돌의 끝.
                if(i == rocks.size()) d = distance - rocks[rocks.size()-1];
                //돌의 중간
                else d = rocks[i] - rocks[removeIdx];
            }
            //지울 조건에 충족 : mid보다 바위간 거리가 작을 때 지운다.
            if(d<mid) removeCount++;
            else removeIdx = i;
        }
        //너무 많이 지웠다. -> 거리를 좀 줄이자
        if(removeCount>n){
            r = mid-1;
 
        }
        //너무 돌을 덜 제거했다. -> 거리를 좀 늘리자.
        else if(removeCount<=n){
            l = mid+1;
            answer = max(answer,mid);
        }
    }
 
    return answer;
}
 
//   int n = 2;
//   vector <int> rocks({2,14,11,21,17})  ;
//   int distance  =25;
//   cout << solution(distance,rocks,n);
// }