[이분탐색] 징검다리

|| 문제설명 ||

1. 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있다. 그리고 그사이에는 바위들이 놓여있다.
2. 바위 중 몇 개를 제거하려고 한다.
3. 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성하라.

• distance : 출발지점부터 도착지점까지의 거리
• rocks : 바위들이 있는 위치를 담은 배열
• n : 제거할 바위의 수

_ distance : 1 이상 1,000,000,000 이하	
_ 바위(= rocks.size()) : 1개 이상 50,000개 이하
_ n : 1 이상 바위의 개수 이하

---

|| 문제해결방법 ||

- rocks의 정렬
- 각 바위들간의 거리의 최소값

---

|| 코드 ||

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0, min = 1, max = distance, mid;
    vector<int> d;
    sort(rocks.begin(), rocks.end());
    for(int i = 0; i < rocks.size(); i++) {
        if(i == rocks.size() - 1) d.push_back(distance - rocks[i]);
        else if(i == 0) d.push_back(rocks[i]);
        else d.push_back(rocks[i+1]-rocks[i]);
    }
    answer = max;
    while(min <= max) {
        int cnt = 0;
        mid = (min + max) / 2;
        for(auto i : d) {
            if(mid > i) cnt++;
        }
        if(cnt < n) min = mid +1;
        else {
            if(mid < answer ) answer = mid;
            max = mid - 1;
        }
    }
    return answer;
}

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0, min = 1, max = distance, mid;
    vector<int> d;
    rocks.push_back(0); rocks.push_back(distance);
    sort(rocks.begin(), rocks.end());
    for(int i = 0; i < rocks.size() - 1; i++) {
        d.push_back(rocks[i+1]-rocks[i]);
    }
    while(n--) {
        vector<int>::iterator idx;
        max = distance;
        for(auto i = d.begin(); i != d.end(); i++) {
            if(*i < max)  {idx = i; max = *i;}
        }
        if (*(idx - 1) > *(idx + 1)) {
            if(idx == d.end() - 1)    *(idx - 1) += *idx;
            else *(idx + 1) += *idx;
        }
        else {
            if(idx == d.begin()) *(idx + 1) += *idx;
            else *(idx - 1) += *idx;
        }
        d.erase(idx);
    }
    sort(d.begin(),d.end());
    answer = d[0];
    return answer;
}

• 예외 발견 : 다른 경우에서 최적의 결과가 나올 수 있음

→ {8, 8}로 answer = 8인 경우가 더 최적