이분탐색 > 징검다리

https://www.welcomekakao.com/learn/courses/30/lessons/43236

 

이 문제도 아직 나한텐 어려운 것 같다.. 또 다른사람의 풀이를 보고나서야 답을 구할 수 있었음 ㅜㅜ

문제를 푸는 로직은 아래와 같다.

 

1. 이분탐색 문제에 맞게 구하려는 값의 최솟값과 최댓값을 정해야 한다. 구하려는 값은 n개만큼의 바위를 제거한 뒤에 남는 바위들 간의 거리의 최솟값중에 최댓값을 구하는 것이다. 즉, 바위간의 거리를 기준으로 삼아야하는 문제이다.

2. 바위간의 거리 중 최솟값은 1이며, 최댓값은 주어진 변수인 distance 로 설정하였다.

3. 중간값인 mid 를 구한다음에 바위의 위치가 담긴 배열을 순회하며 구한 mid 값보다 이전 바위의 거리가 작으면 제거하고, 같거나 크다면 바위를 제거하지 않는다. 이때 제거 한 바위의 갯수를 카운트하고 제거하지 않았다면 바위의 index 를 저장한다.
(그 이유는 제거하지 않은 바위(lastRocksIdx)와 다음 번(i)에 선택 된 바위와의 거리를 계산하기 위함이다.)

4. 마지막으로 제거한 바위의 갯수가 n개보다 크다면 우리가 지정한 바위간의 거리(mid)가 너무 크기때문에 이를 줄여야 하므로 right 위치를 수정한다. 그와 반대로 제거한 바위의 갯수가 작다면 바위간의 거리(mid) 가 너무 작은 것이기 때문에 left 의 위치를 수정하여야 한다.

4번에서 주의해야할 점은 아래와 같다.
27 line 의 조건문을 remove <= n 으로, 29 line 의 조건문을 remove < n 으로 변경한 뒤에 31 line 의 정답을 구하는 부분을 27 line 의 if 문 내부로 넣었을 시엔 정답이 도출되지 않는다. 그 이유는 문제에 나와있듯이 바위를 제거한 뒤 지점간의 거리 중 최솟값중의 최댓값을 찾는 것이기 때문에 위처럼 변경한다면 최댓값중에 최솟값을 찾게 되는 꼴이되버린다. 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    
    int left = 1;
    int right = distance;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        int remove = 0;
        int lastRocksIdx = -1;
        for (int i = 0; i <= rocks.size(); ++i) {
            int d = lastRocksIdx == -1 ? rocks[i] : 
            i == rocks.size() ? distance - rocks.back() : rocks[i] - rocks[lastRocksIdx];
            
            if (d < mid) {
                remove++;
            }
            else lastRocksIdx = i;
        }
        
        if (remove > n) {
            right = mid - 1;
        } else if (remove <= n) {
            left = mid + 1;
            answer = answer < mid ? mid : answer;
        }
    }
    
    return answer;
}