[Programmers] 징검다리

이분탐색을 활용하는 문제였다.

맨처음 문제를 접하였을 때 부술수 있는 바위를 고르는 방법을 우선적으로 생각했는데, 바위의 갯수가 50,000이기 때문에 50000C2 라는 조합을 한다면 시간초과가 날것이라고 생각했다. 그래서 다른 바위말고 distance를 기준으로 문제를 접근해보았고 distance가 1,000,000,000으로 주어졌기 때문에 시간복잡도가 효율적인 이분탐색을 사용해보았다. 

low값을 바위사이의 최소 거리인 1, 그리고 high값을 바위 사이의 최대거리인 distance로 두고, 이분탐색을 돌면서 mid 값보다 크거나 같도록 바위를 배열하게 된다면 몇개의 바위를 부숴야 하는지 확인하고, 바위를 부술 수 있는 최대값 n 과 비교하여 바위 사이의 최대 간격을 찾는 방법으로 문제를 해결해보았다. 즉 다음과 같은 로직으로 접근하였다.

package algostudy2;
 
import java.util.Arrays;
 
public class Solution_징검다리 {
    public static void main(String[] args) {
        // int distance = 25;
        // int[] rocks = {2, 14, 11, 21, 17};
        // int n = 2;
        int distance = 16;
        int[] rocks = {4, 8, 11};
        int n = 2;
 
        System.out.println(solution(distance, rocks, n));
    }
 
    static int solution(int distance, int[] rocks, int n) {
        int rocksLen = rocks.length;
 
        //시작점, 끝점, 모든 바위가 저장된 arr 배열
        int[] arr = new int[rocksLen + 2];
        for (int i = 0; i < rocksLen; i++) {
            arr[i] = rocks[i];
        }
 
        //시작점, 끝점
        arr[rocksLen] = 0;
        arr[rocksLen + 1] = distance;
 
        int arrLen = arr.length;
        Arrays.sort(arr);
 
        int low = 1;
        int high = distance;
 
        int answer = 0;
 
        while (low <= high) {
            //점프할 거리를 mid로 설정
            int mid = (low + high) / 2;
            // System.out.println(mid);
 
            boolean isPossible = true;
            int destory = 0;
 
            //전체 arr에 대해 mid 만큼 점프하면서 몇개의 바위를 제거해야지 mid 만큼 점프할수 있는지 확인
            for (int i = 0; i < arrLen && isPossible; i++) {
                int startIndex = i;
                int nextIndex = i + 1;
                while (true) {
                    if (nextIndex == arrLen) {
                        break;
                    }
 
                    int dis = arr[nextIndex] - arr[startIndex];
 
                    if (dis < mid) {
                        destory += 1;
                        nextIndex += 1;
                    } else {
                        break;
                    }
                }
 
                //제가한 바위 수가 n 보다 크면 불가능
                if (destory > n) {
                    isPossible = false;
                }
 
                //for문에서 i++가이루어지기 때문에 -1 처리
                i = nextIndex - 1;
            }
 
            //가능하다면 갱신하면서 최대값을 찾기
            if (isPossible) {
                answer = Math.max(answer, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
 
        }
 
        return answer;
    }
}