[Programmers] 징검다리

난이도 : Level 4

문제링크

• 출발지부터 distance 만큼 떨어진 도착지점이 있고 그 사이에는 바위들이 놓여 있다.
• 최대 n개의 바위를 제거하였을 때, 각 바위 사이의 거리의 최솟값 중 가장 큰 값을 리턴하라.

 

해설

1. 바위 사이의 거리의 최솟값중 최댓값을 이분탐색

public int solution(int distance, int[] rocks, int n) {
    long left = 1, right = distance, mid = 0, answer = 0, prevRock = 0, rockCount = 0;
    Arrays.sort(rocks);

    while (left <= right) {
        mid = (right + left)/2;
        prevRock = 0;
        rockCount = 0;

        for (int rock : rocks) {
            if (mid > rock - prevRock) rockCount++;
            else prevRock = rock;
        }

        if (mid > distance - prevRock) rockCount++;

        if (n >= rockCount) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return (int) answer;
}

• 바위간의 사이를 모두 조사하여, 주어진 사이 거리보다 크면 바위를 제거한다.
• 제거된 바위의 수가 n보다 작거나 같다면, 최댓값을 늘린다
• 제거된 바위의 수가 n보다 크다면, 최댓값을 줄인다