[프로그래머스][level4] 징검다리 (C++)

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

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

 

[난이도] level4
[유형] 이분탐색

[풀이]
바위가 최대 50000개이기 때문에 이중 n개를 고른 모든 경우를 해보면 시간초과가 발생합니다.

distance가 최대 10억 이하인데 이렇게 큰 수가 주어진 경우 이분탐색을 의심해볼 수 있습니다.

1) rocks 는 오름차순으로 정렬해줍니다.
2) low를 0 high를 distance+1로 놓습니다.

3) 매 탐색에서 나오는 mid를 이용해
   "바위들간의 가장 가까운 거리는 기껏해야 mid이다"
   이렇게 정의를 하면 0 -> rocks[0] -> rocks[1]... 순으로 방문할 때
   rocks[j]-rocks[i]의 거리가 mid보다 멀면 rocks[j]는 제거된 바위로 간주하면 됩니다.

   i) 남아있는 바위의 개수가 rocks.size()-n (남아있어야할 바위의 개수) 보다 크다면,
   mid를 조금 더 큰 수를 사용해볼 수 있기 때문에 mid=lo 로 업데이트 하고 다음 시행으로 넘어갑니다.
   (잘 생각해보면 mid가 커질수록 남아있는 바위의 수는 적어지고,
   mid가 작아질수록 남아있는 바위의 수는 커지기 때문입니다.)

   ii) 남아있는 바위의 개수가 rocks.size()-n보다 더 적다면
   바위를 더 남겨야합니다. 그러려면 mid를 더 줄여서 더 간격이 좁은 바위도 포함될 수 있도록 해야합니다.
   hi=mid로 업데이트 해주고 다음 시행으로 넘어갑니다.

   위의 시행을 반복하다보면 lo와 hi가 1 차이가 나는 상황까지 수렴하게 됩니다.
   이때의 lo 값이 최적의 값이므로 이 값을 return하면 됩니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(),rocks.end());
    int lo=0, hi=distance+1;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        int cnt=0;
        int cur=0;
        for(int i=0;i<rocks.size();i++){
            if(rocks[i]-cur>=mid) {
                cnt++;
                cur=rocks[i];
            }
        }
        if(cnt>=rocks.size()-n) lo=mid;
        else hi=mid;
    }
    return lo;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/징검다리.cpp