[프로그래머스 Lv4] : 징검다리

문제 링크

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

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

바위를 n개 제거했을 때, 각 지점 사이의 거리의 최솟값이 최대가 되도록 바위를 제거하는 문제.

 

풀이

• 풀이 알고리즘

각 지점들 사이에 벌어져야할 최소 간격을 "이분탐색"을 통해서 탐색한다.

벌어저야할 간격의 범위는 0 ~ distance 이내 일 것이다.

L = 0, R = distance로 잡고 mid 값을 지점들 사이 벌어져야할 최소 간격이라고 생각한다.

 

1. 먼저, 각 지점들의 위치가 불규칙하게 주어지므로 sort 함수를 통해 오름차순으로 정리해준다.

2. 각 지점사이가 최소 mid 만큼 벌어지기 위해서는 몇 개의 지점을 지워야하는 지 센다.

벌어져야하는 최소 간격이 커질수록 지워야할 바위가 많아질 것이다.

=> 그래야 간격이 벌어지니까

만약 지워야할 바위의 수가 n개보다 많다?? => 너무 많이 지워야하므로 간격을 좁혀야한다.

이때는 R = mid - 1로 설정해서 mid 값이 작아질 수 있도록 유도한다.

반대로 지워야할 바위의 수가 n개보다 적거나 같다?? => 이때의 간격은 유효한 값이고 간격을 더 벌려봐도 된다.

이때는 L = mid + 1로 설정해서 mid 값이 커질 수 있도록 유도한다.

 

유효한 간격들 중에 가장 큰 값을 리턴해주면 되는 문제.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int binary_search(int distance, vector<int> rocks, int n){
    int L = 0;
    int R = distance - 1;
    int ret = 1;
    while(L <= R){
        int now = 0;
        int mid = (L+R)/2; // 바위 사이 최소 mid 만큼 간격이 벌어져야함
        int cnt = 0;
        for(int i = 0; i<rocks.size(); i++){
            if(rocks[i] - now >= mid){
                cnt++;
                now = rocks[i];
            }
        }
        //rocks.size() - cnt 개를 지워야 mid 간격 유지가능
        
        if(rocks.size() - cnt <= n){
            L = mid + 1; //간격을 더 벌려봐도 됨
            ret = max(ret, mid);
        }
        else if(rocks.size() - cnt > n) // 더 많이 지워야함 => 간격을 좁혀야함
            R = mid - 1;
    }
    return ret;
}
 
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    answer = binary_search(distance, rocks, n);
    return answer;
}