징검다리 문제 링크
리뷰
코딩테스트 고득점 키트의 '이분탐색'카테고리에 있는 문제다.
바위 중에 n개를 제거했을 때, 바위 간 거리의 최소값중에서 최대가 되는 값이 답이 된다.
도착 위치는 distance로 주어지고, 출발 위치는 항상 0이다.
만약 바위가 1개인데 위치가 5 라면, 바위 간 거리는 0~ 5, 5 ~ distance 를 비교한다.
둘 중에 거리차이가 최대인게 답이다.
도착 위치 distance 는 1이상 1억 이하다. 따라서 이분탐색으로 범위를 빠르게 좁혀줘야 한다.
이분 탐색의 대상은 '거리의 최소값' 이다.
바위 위치 배열을 오름차순 정렬 하고, 거리의 최소값이 mid를 만족하는지 모든 바위에 대해 검사한다.
바위 n개를 제거하면서, 모든 바위간의 거리의 최소값이 mid임을 만족해야 한다.
바위 간의 거리차이가 mid 미만이라면, 조건을 만족하니까 제거한 바위 카운팅을 증가시킨다.
만약, 제거한 바위가 n개를 초과한다면, 거리의 최소값 mid 크기를 줄여야한다.
n개 이상을 제거 해야 거리의 최소값이 mid 임을 만족시킨다는 의미이기 때문이다.
"맞았습니다" 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
sort(rocks.begin(), rocks.end()); // 오름차순 정렬
int rlen = rocks.size(), answer = 0;
int left = 0, right = distance;
// 거리의 최소값이 mid 이하인지 검사한다.
while(left <= right){
int mid = (left + right ) /2; // 거리의 최소값
int prev_idx = 0; // 직전 바위의 위치
int remove_cnt = 0; // 제거한 바위 개수
for(int i = 0; i < rlen; i++){
if(rocks[i] - prev_idx < mid) { // 거리 차이가 mid 이하라면 제거한다.
remove_cnt++;
}else{
prev_idx = rocks[i];
}
}
// 도착지점과 마지막바위 간의 거리차이가 mid 이하라면 제거
if(distance - prev_idx < mid) remove_cnt++;
if(remove_cnt <= n) {
answer = max(mid, answer); // n개 이하로 제거했다면, 거리의 최소값을 증가시켜본다.
left = mid + 1;
} else{
right = mid - 1; // 거리의 최소값을 더 줄여본다.
}
}
return answer;
}
