[프로그래머스] 징검다리 - 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		return
25	[2, 14, 11, 21, 17]	2	4

입출력 예 설명

문제에 나온 예와 같습니다.

---

풀이

솔직히 말하자면 문제 자체가 분류되어 있지 않았다면 이분 탐색으로 풀 생각을 못했을 것이다. 또한, 이분 탐색으로 문제를 접근하려고 해도 어떤 값을 기준으로 탐색을 해야할지도 고민이었던 문제였다.

 

https://taesan94.tistory.com/154 의 글을 참고하여 문제를 해결하였다.

 

중요한 것은 관점의 전환이 필요했다는 것. 바위를 n만큼 제거하고 각 바위들 사이의 거리를 구한다는 관점이 아닌 바위 간의 거리의 최솟값이 x라고 할 때 바위를 몇 개 제거되어야 하는지를 생각했어야 했다.

 

바위 간의 거리 최솟값을 이분 탐색의 기준으로 삼는다.

바위 간거리의 최솟값이 left와 right의 중간값 mid일 경우

제거해야하는 바위의 갯수(removedRock)가 n 보다 크다면 right를 mid - 1로 변경하여 탐색을 진행하고,

제거해야하는 바위의 갯수(removedRock)가 n 보다 작거나 같다면 left를 mid + 1로 변경하여 탐색을 진행한다. (n과 같다면 answer에 최대값을 저장한다.)

 

제거해야하는 바위의 갯수는 현재 위치(before)에서 다음 바위 사이의 거리가 mid보다 작은 경우에 카운팅한다.

현재 위치(before)에서 다음 바위 사이의 거리가 mid보다 작다는 건 기준으로 삼은 바위 간의 거리 최솟값보다 짧은 거리라는 것으로 바위가 사라져야만 기준 최솟값을 맞출 수 있다.

 

코드

import java.util.Arrays;

public class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;

        Arrays.sort(rocks);

        int left = 1;
        int right = distance;

        while (left <= right) {
            int mid = (left + right) / 2;
            int removedRock = 0;
            int before = 0;

            for (int rock : rocks) {
                if (rock - before < mid) {
                    removedRock++;
                    continue;
                }

                before = rock;
            }

            if (distance - before < mid) {
                removedRock++;
            }
            
            if (removedRock > n) {
                right = mid - 1;
                continue;
            }

            answer = Math.max(answer, mid);
            left = mid + 1;
        }

        return answer;
    }
}