[프로그래머스] 징검다리 43236 (JAVA)

풀이방식

1. 바위 위치 배열 정렬
2. 바위 사이 간격 배열 구하기
3. 이분탐색 진행

포인트

이분탐색 설정

거리를 구하는 문제이므로 거리를 기준으로 탐색
거리보다 적은 간격을 가진 바위 제거
제거한 바위 개수가 n이 될 때까지 탐색 진행

구현

import java.util.Arrays;

public class NUM43236 {
    public static void main(String[] args) {
        int distance = 25;
        int[] rocks = {2, 14, 11, 21, 17};
        int n = 2;

        System.out.println(solution(distance, rocks, n));
    }

    public static int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);

        int[] distances = new int[rocks.length+1];
        distances[0] = rocks[0];
        for(int i = 1 ; i < rocks.length ; i++){ distances[i] = rocks[i] - rocks[i-1]; }
        distances[distances.length-1] = distance - rocks[rocks.length-1];

        int start = 0;
        int end = distance+1;
        while(start < end){
            int mid = (start + end)/2;
            int remove = 0, current = 0;
            for(int i = 0 ; i < distances.length ; i++){
                current += distances[i];
                if(current < mid){ remove++; }
                else { current = 0; }
            }

            if(remove < n){ start = mid+1; }
            else if(remove > n){ end = mid; }
            else { start = mid+1; }
        }

        answer = start-1;
        return answer;
    }
}

미해결

current 변수가 가진 의미

---

*다른 분들의 코드를 참고하여 작성했습니다