programmers 징검다리 c++

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

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

 

이분탐색 l4 문제인 징검다리 입니다.

이분탐색에 해당하는 문제를 풀 때는

이분탐색의 구간에 해당하는 것이 무엇인지, 이를 판단하는 조건은 무엇인지 파악하는 것이 중요합니다.

문제에서 주어졌듯이 이분탐색의 '구간'에 해당하는 것, 즉 원하는 값은

각 돌 사이의 간격이며 이 간격들 중의 최솟값을 최대로 하는 것입니다.

이를 판단하는 조건은 n개의 돌을 제거하는 것!

 

여기서 아래와 같이 생각해볼 수 있습니다.

나열된 여러 개의 돌 중에서 n개를 제거하면서 돌 사이 간격의 최솟값을 최대로 하고 싶다

=> n개의 돌을 제거한 이분탐색의 결과값인 '간격'을 알고 싶다

=> 임의의 '간격'을 기준으로 돌을 제거할 수 있을까

=> 임의의 '간격'보다 작은 '간격'에 해당하는 돌을 제거하면서 몆개를 제거할 수 있는지 확인한다

==> 만약 제거한 돌의 갯수가 n개보다 작다면?

===> 이것은 괜찮다. 일단 모든 돌의 간격을 '간격' 이상으로 유지했다는 뜻이니까

         n개가 될 수 있게 더 제거해도 된다는 의미가 된다.

==> 만약 제거한 돌의 갯수가 n개보다 크다면?

====> 이것은 안된다. 모든 돌의 간격을 원하는 '간격' 기준만큼 유지할 수 없다는 뜻이니까

=> 제거한 돌의 갯수가 n개이하라면 모든 돌의 간격은 원하는 기준값인 '간격' 보다 크거나 같아진다.

=> 최솟값의 최댓값을 찾기 위해 제거한 돌의 갯수가 n개 이하라면 기준값을 늘려보고

=> 제거한 돌의 갯수가 n개를 초과한다면 기준값을 줄여본다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool canDelete(vector<int> v, int mid, int n){
    int deleteRock = 0;
    int leftIdx = 0;
    int rightIdx = 1;
    while(rightIdx < v.size()){
        if(deleteRock > n) break;
        int dist = v[rightIdx] - v[leftIdx];
        if(dist < mid){
            deleteRock++;
            rightIdx++;
        }
        else{
            leftIdx = rightIdx++;
        }
    }
    
    if(deleteRock <= n) return true;
    else return false;
}

int solution(int distance, vector<int> rocks, int n) {
    rocks.push_back(0);
    rocks.push_back(distance);
    sort(rocks.begin(), rocks.end());
    
    int left = 1, right = 1000000000, mid;
    int answer = left;
    
    while(left<=right){
        mid = (left+right)/2;
        if(canDelete(rocks, mid, n)) {
            left = mid+1;
            answer = max(answer, mid);
        }else right = mid-1;
    }
    
    return answer;
}