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

 

문제

바위들의 위치가 담긴 배열이 있고, 제거할 바위 수 n가 있다.

바위 배열에서 n개를 제거한 이후 각 지점사이 거리 최솟값 중 가장 큰 값 리턴해라.

- distance : 도착지점까지의 거리 1~10억

- rocks 요소 개수 : 1~5만

- n 제거할 바위 개수 : 1 ~5만

 

1) 조합

처음엔 단순하게 n개의 숫자 중 n개를 고르는 시행 만든 뒤 최댓값을 비교하는 방식이 떠올랐다.

하지만 input 값이 커진다면 조합의 경우의 수가 매우 커지기 때문에 효율적인 방식이 아니다.

 

2) 이진탐색

최소거리를 탐색기준으로 설정한 뒤

추정한 거리로 바위 개수를 세고, '추정한 바위 개수' >= '바위 총개수 - n' 가 남아있어야 최소거리 조건을 만족한다. 

조건을 만족한 값들 중 최댓을 구해서 리턴하면 된다.

*isPossible()의 curr 초기화에서 좀 헤맸다. 1번 바위를 반드시 고르는 것이 아니므로 curr= 추정한 최소거리. 로 초기화한 후 시작해야 함

 

 

 

코드

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int distance = 25;
        int[] rocks = {2, 14, 11, 21, 17};
        int n = 2;
//        Arrays.sort(rocks);
        System.out.println(solution(distance, rocks, n));
    }

    static int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        long smallest = 1, biggest = distance; // 범위 설정

        int answer = 0;
        while (smallest <= biggest) {
            long mid = (smallest + biggest) / 2;
            if (isPossible(mid, rocks, n)){
                answer = (int) Math.max(mid, answer);
                smallest = mid + 1;
            } else{
                biggest = mid - 1;
            }
        }

        return answer;
    }

	
    static boolean isPossible(long target, int[] rocks, int n){
        long curr = target;
        int rock_cnt = 0;
        for (int i = 0; i < rocks.length; i++) {
            if (curr <= rocks[i]){
                rock_cnt++;
                curr = rocks[i] + target;
            }
        }
        return rock_cnt >= rocks.length - n; // check
    }
}