프로그래머스. 징검다리(c++) / 이분탐색

약간 생각의 전환이 필요한 이분탐색 문제였다.

 

mid값을 '돌사이의 최솟값'이라고 잠정적으로 잡아놓은 후에,

mid값보다 (현재 돌 위치-이전 돌 위치)값이 더 작으면, 돌을 없애고 더 크면, 돌을 살려둔다.

 

그 후, 없앤 돌의 수가 n보다 작거나 같다면 mid(돌 사이의 최솟값)이 충분히 작다는 의미니 low = mid+1을 해주고

n보다 크다면 mid값이 너무 크다는 의미니 high = mid-1로 해준다.

.....이런식으로 이분탐색을 진행하면 된다.

 

 

이 문제도 그림으로 설명하면 좋을 것 같아서 추후 첨부해보겠다.

 

 

코드 첨부

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int low = 0;
    int high = distance;
    
    sort(rocks.begin(), rocks.end());
    
    while(low<=high){
        int prev = 0; // 이전의 돌 위치
        int remove_num = 0;
        int mid = (low+high)/2; // '돌사이의 최솟값'을 잠정적으로 잡아놓는다.
        
        for(int i=0; i<rocks.size(); i++){
            if((rocks[i]-prev)<mid){ // 돌을 제거
                remove_num++;
            }else{ // 돌을 그냥 둔다.
                prev = rocks[i];
            }
        }
        
        // 마지막 distance와도 비교해준다.
        if((distance-prev)<mid){
            remove_num++;
        }
        
        if(remove_num<=n){
            // 갱신
            answer = max(answer, mid);
            low = mid+1;
        }else{
            high = mid-1;
        }
    }
    
    return answer;
}

 

문제 첨부

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

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