이분탐색을 활용한 알고리즘 문제풀이

오늘 또 푼 문제: 징검다리

입출력

• 입력: 출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어집니다.
• 출력: 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 합니다.

예제 코드

import java.util.*;

class Solution {
    /**
     * 0. 시작점과 도착점을 배열에 추가
     * 1. 0과 distance를 각각 lt와 rt로 설정하여 n개의 돌을 뺐을 때의 돌들 간의 최대 거리를 설정
     * 2. 이전 돌들이 연속하여 건너뛴 경우를 반영하기 위하여 extraGap변수 활용
     * 3. 배열에 loop를 돌며 해당 돌과 전 돌과의 거리가 mid보다 작을 경우 카운트와 연속하여 건너뛴 횟수 증가
     * 4. 만약 n번 이상 돌을 건너 뛰었다면 반복문을 종료
     * 5. 건너뛴 횟수가 n번 이하일 경우 최대 거리를 더 크게 설정
     * 6. 초과일 경우 해당 거리를 더 작게 설정
     */
    public int solution(int distance, int[] rocks, int n) {
        int[] arr = new int[rocks.length + 2];
        arr[0] = 0;
        for (int i = 1; i < arr.length - 1; i++) arr[i] = rocks[i - 1];
        arr[arr.length - 1] = distance;
        int answer = 0, lt = 0, rt = distance, len = arr.length;
        Arrays.sort(arr);
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            int cnt = 0, extraGap = 0;
            for (int i = 1; i < len; i++) {
                int gap = arr[i] - arr[i - 1 - extraGap];;
                if (gap < mid) {
                    cnt++;
                    extraGap += 1;
                } else extraGap = 0;
                
                if (cnt > n) break;
            }
            if (cnt <= n) {
                answer = Math.max(answer, mid);
                lt = mid + 1;
            } else rt = mid - 1;            
        }
        return answer;
    }
}

• 돌을 n개 빼서 해당 최대 거리가 mid보다 큰지 작은지를 확인하며 이진탐색을 진행하였습니다.

회고

• 과연 저는 이진트리라는 힌트를 받지 않았다면 풀 수 있었을까요?