[이분 탐색, 난이도 상] 프로그래머즈, 징검다리

출발지점부터 도착지점 사이에 놓여져 있는 돌들 중에서 n개를 뺀 상태의 모든 경우에서, 각 지점 사이의 거리들의 최솟값들중 가장 큰 값을 구하면 되는 문제이다.

 

rocks의 순서는 뒤죽박죽 하기 때문에 오름차순으로 정렬해주고 시작해야 한다.

 

우리가 구해야 하는 답(바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값) 을 미리 적당한 값으로 세워두고, 실제 정답이 미리 세워둔 값보다 큰지 작은지 판단하고 범위를 좁혀 나가면 된다.

바위를 몇개 제거해야 미리 세워둔 답이 실제 정답이 될 수 있는지 계산하는 것이 핵심이다. 그 바위 수는 n개가 나와야 하는 것이다.

 

입출력 예를 예로 들어보자.

정렬된 바위의 배치 -> [2,11,14,17,21]

각 지점 사이의 거리 (시작점, 도착점도 지점이라고 함) -> [2,9,3,3,4,4]

distance의 중간정도인 12를 답으로 가정하고 범위를 좁혀 나가기로 한다. (mid=12)

각 지점 사이의 최솟값이 12가 되어야 한다는 의미이기 때문에, 지점 사이가 12미만이 되는 지점의 돌을 모두 빼버린다.

그럼 모든 지점의 돌이 빠지게 되는데

빠진 돌의 개수는 2(n의 값)를 넘으므로, 빠진 돌의 개수를 2에 맞추기 위해서는 mid의 값은 12보다 작아야 한다는 사실을 알 수 있다.

가능한 정답의 범위는 0~11로 좁혀지게 되고 새로운 mid값은 이 범위의 중간정도인 5로 재설정하며 범위의 크기가 1이 될 때까지 이 과정을 반복하면 된다.

 

빠진 돌의 개수가 2이하라면 정답은 현재의 mid의 값 이상이어야 하기 때문에, 가능한 정답의 범위의 최솟값을 mid+1로 좁혀주면 된다. 그리고 이 문제에서 원하는 것은 최댓값이기 때문에 이 선택문에서 최댓값 갱신 코드를 작성해주면 된다.

 

테스트 케이스 9개 모두 통과

 

#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    int mini = 0;
    int maxi = distance;
    int mid;
    int base, coun; 
    // base:지점 탐색 기준점, coun:빼낸 돌의 수
    sort(rocks.begin(),rocks.end());
    while(mini<=maxi){
        mid = (mini+maxi)/2;
        base=0;
        coun=0;
        
        //지점 사이가 mid 미만인 지점의 돌을 모두 빼버리기
        for(int i=0;i<rocks.size();i++){
            if(rocks[i]-base<mid) coun++;
            else base = rocks[i];
        }
        if(distance-base<mid) coun++; //마지막 지점 처리
        
        //범위 좁히기
        if(coun>n) maxi=mid-1;
        else {
            mini=mid+1;
            answer = max(answer,mid);
        }
    }
    return answer;    
}