[Programmers] 징검다리

징검다리

문제 설명

출발지점부터 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~dist가 범위라고 생각하였고 여기서 이진탐색을 해야한다고 생각했다. 하지만 기준을 무엇으로 잡아야할지..(처음에는 그 범위에 있는 바위에 갯수라고 생각했었다.) 끝까지 모르겠어서 결국 3시간 정도 고민하고 나서 구글링을 하였다.

여기서 기준을 바위 사이의 최소 거리로 두는 것이다. 즉, 바위 사이의 최소 거리를 정해두고, 기준 최소 거리보다 작으면 제거한다고 생각한다. 이 때 제거하는 바위의 수를 세어 n값보다 크면 high값을 줄이고, n값보다 작으면 low값을 늘린다. (여기서는 기본 이진탐색의 개념이다.)

코드

class Solution {

    int removeRocks(int distance, int[] rocks, int mid) {
        int result = 0;
        int last = 0;

        for (int i = 0; i <= rocks.length; i++) {
            int gap = (i != rocks.length ? rocks[i] - last : distance - last);
            if (gap < mid) {
                result++;
            } else {
                if (i == rocks.length)
                    break;
                last = rocks[i];
            }
        }
        return result;
    }

    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int low = 1;
        int high = distance;
        int mid = 0;
        Arrays.sort(rocks);
        while (true) {
            if (low > high) {
                break;
            }
            mid = (low + high) / 2;
            if (removeRocks(distance, rocks, mid) > n) {
                high = mid - 1;
            } else {
                answer = mid;
                low = mid + 1;
            }
        }

        return answer;
    }
}