징검다리 - Level4

programmers.co.kr/learn/courses/30/lessons/43236

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

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    
    
    sort(rocks.begin(), rocks.end());
    
    int left =0;
    int right = distance;
    
    while(left <= right){
        
        
        int mid = (left+right)/2; // mid는 최솟값을 정하는 것 
        
        int cnt =0;   // mid가 최소값이 되기 위해서 없애야하는 바위의 수 
        int prev = 0; //이전 바위의 위치 
       
        for(int i=0; i<rocks.size(); i++){
            
            if(rocks[i]-prev < mid){cnt++;} // 다른 바위의 사이 거리가 mid 값보다 작은 경우에는 없애야하는 바위의 수를 증가 시킨다.
            else{prev = rocks[i];} // 만약에 없애도 되지 않은 경우에는 이전 바위의 위치를 바꾸어준다. 
            
        }
        
        if(distance-rocks[rocks.size()-1]<mid){cnt++;} //마지막 바위와 마지막 사이의 거리도 mid 값과 비교해본다. 
        
        if(cnt<=n){ // 없애야할 바위수가 n개보다 작거나 같을 때 -> mid가 더 큰 수일 경우를 탐색해야 함.
            answer = mid;
            left = mid+1;
        }
        else{  // mid 가 더 작은 수일 경우를 탐색해야함 .
            right = mid-1;
        }
        
        
        
    }

    
    
    return answer;
}