[이분탐색] 징검다리

프로그래머스

 

이분탐색문제다. 뭘 어떻게 비교해야 하는지 헷갈려서 감이 안 올 수도 있는데 기준만 명확히 잡으면 금방(????) 풀 수도 있는 문제다. 

 

우선 이분탐색의 범위는 바위 사이의 거리의 최소값이다. 

 

바위 사이의 거리의 최소값 middle을 기준으로 middle보다 거리가 작으면(최소값보다 작으면 안 되니까!!) 제거할 바위의 개수를 늘려준다. 이때 주의할 점은 다음에 비교할 바위를 이전에 제거한 바위의 거리와 합해서 생각해야 한다!!!

 

 

처음으로 2를 제거해보자

2를 제거했으므로 다음 순서는 11이다. 하지만 2가 제거가 됐으므로 2번 바위와 11번 바위의 블럭을 계산하는 게 아니라 0번 바위와 11번 바위의 거리를 생각해야 한다.

 

따라서 currentDistance = 2 + 9 = 11이며, 11이 middle보다 작은지 확인해야 한다.

 

11번 바위 역시 제거할 수 있다. 거리가 11보다 작기 때문이다.

 

이제 다음은 14번 블럭이다 14번 블럭은 제거된 바위들의 합과 비교했을 때 13보다 크다. 14번 바위는 제거할 수 없다. 따라서 다음에 비교해야 할 블럭은 이전 바위의 거리와는 상관 없으므로 currentDistance = 0으로 생각해야 한다.

 

 

이와 같은 방법으로 바위는 한 개밖에 제거할 수 없다.

 

하지만 우리는 총 2개의 바위를 제거해야 한다. 따라서 remove(=1)과 n(=2)를 비교했을 때 remove가 더 작으므로 바위의 최소값을 줄여줘야한다!

 

이 과정을 전체코드로 다음과 같이 나타낼 수 있다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    
    vector<int> distances;
    
    sort(rocks.begin(), rocks.end());
    
    distances.push_back(rocks[0]);
    
    for(int i = 0; i < rocks.size() - 1; i++) {
        distances.push_back(rocks[i + 1] - rocks[i]);
    }
    
    distances.push_back(distance - rocks[rocks.size() - 1]);
    
    int start = 0;
    int end = distance;
    
    while(start <= end){
        int middle = (start + end) / 2;
        
        int c = 0;
        int currentDistance = 0; 
        
        for(int d : distances){
            currentDistance += d;
            if(currentDistance < middle){
                remove++;
            } else{
                currentDistance = 0;
            }
            
        }
        
        if(remove > n) end = middle - 1;
        else start = middle + 1;
        
        cout << endl;
    }
    
    return end;
}​