[프로그래머스/이분탐색] Level 4 징검다리 (JAVA)

문제

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

---

풀이

1. 각 지점 사이의 거리의 최솟값을 기준으로 이분탐색을 진행한다.
2. left는 distance의 최솟값인 1, right는 distance의 최댓값인 10억이다.
3. isAvailable()에서 rocks 배열을 차례대로 탐색하며 target을 만들기 위해 돌을 제거한다.
4. 돌을 제거한 개수가 주어진 n 이하이면 available한 것이다.
5. 더 큰, 혹은 더 작은 distance에 대해 이분탐색을 계속 진행한다.
6. 최종적으로 얻은 answer가 최솟값 중 최댓값이 된다.

이번 문제에서는 isAvailable() 메소드를 내 스스로 힘으로 만들어내지 못했다.. 슬프다..

rocks에서 돌을 직접 빼면서 removalCount를 체크한다는 발상이 정말 경이로울 정도다. 어떻게 하면 이렇게 뚝딱 떠올릴 수 있는 걸까... 이걸 검색해서 풀 수밖에 없었던 나의 실력이 한탄스러울 뿐이다.

또 지금 생각해보면 최댓값 중 최솟값 이라는 말에 힌트가 있는 것 같다. 최댓값은 solution()의 이분탐색 while문 안에서 찾는 것이기 때문에 isAvailable()에서는 최솟값을 찾아 주면 되었기 때문이다.

---

코드

import java.util.Arrays;

class Solution {
    
    private static int MIN_DISTANCE = 1;
    private static int MAX_DISTANCE = 1000000000;

    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);
        int left = MIN_DISTANCE;
        int right = MAX_DISTANCE;
        int answer = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (isAvailable(distance, rocks, n, mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }

    private boolean isAvailable(int distance, int[] rocks, int n, int target) {
        int removalCount = 0;
        int previous = 0;
        for (int rock : rocks)
            if (rock - previous < target) removalCount++;
            else previous = rock;
        if (distance - previous < target) removalCount++;
        return removalCount <= n;
    }
}

---

참고

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