[프로그래머스 43236] 징검다리

문제풀이

문제 자체가 이분탐색인걸 알고푸는데도 이분탐색의 기준을 찾는 데 힘들었다..

인터넷에서 풀이에대한 힌트를 참고하고 문제를 풀었다. 

 

최소거리를 기준으로 계속 이분탐색을 진행한다.

현재 mid값이 현재 추정한 거리이고 

 

해당 mid값보다 돌사이의 거리가 작은경우에는 바위를 제거 큰 경우에는 거리 최소값을 저장한다. 

 

그리고 기준에 맞게 모든 바위를 제거한후 거리를 판단하여 제거가 더많이 되었으면 거리를 줄이고 

제거가 기준보다 적게되었으면 거리 기준을 높인다.

 

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = INT_MAX;
    
    int left=0,right=distance;
    
    sort(rocks.begin(),rocks.end());
    
    
    while(left<=right){
        
        int prev =0;// 시작지점
        int mid = (left+right)/2;
        int removed_cnt=0;
        int min_distance = INT_MAX;
        for(int i=0;i<rocks.size();i++){
            if(rocks[i] - prev < mid)
                removed_cnt++;
            else{
                min_distance = min(min_distance, rocks[i] - prev);
                prev = rocks[i];
            }
        }
        
        if(removed_cnt > n){ //제거해야될 수보다 더많이 제거했을때. 거리를 줄여야됨
            right = mid-1;
        }
        else{ // 제거한 돌의 개수가 기준보다 적다. 거리 기준을 높여야 된다.
            answer = min_distance;
            left = mid + 1;
        }
    }
    
    
    return answer;
}

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스