[프로그래머스/JAVA] Lv.4 - 징검다리

프로그래머스 Lv.4 - 징검다리

요구사항

• 바위 n개를 제거했을 때 출발점, 도착점, 바위 간 거리의 최솟값을 최대화하는 문제

접근 방식

• 이분탐색 대상: 거리의 최솟값 (1 ~ distance)
• mid가 정해지면 왼쪽부터 순회하며 이전 바위와의 거리가 mid보다 작으면 제거(count++)
• 조건: count <= n 이면 가능 → lt = mid + 1, answer 갱신
• 조건: count > n 이면 불가능 → rt = mid - 1

코드

import java.util.*;

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

        int[] arr = new int[rocks.length + 1];
        for (int i = 0; i < rocks.length; i++) arr[i] = rocks[i];
        arr[rocks.length] = distance;
        Arrays.sort(arr);

        int lt = 1, rt = distance;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            int before = 0, cnt = 0;

            for (int x : arr) {
                if (x - before < mid) {
                    cnt++;
                } else {
                    before = x;
                }
            }

            if (cnt <= n) {
                lt = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                rt = mid - 1;
            }
        }
        return answer;
    }
}

느낀점

• "최솟값을 최대화 / 최댓값을 최소화" 키워드가 나오면 파라메트릭 서치를 떠올리자.
• 큰 수를 누적하는 경우 항상 자료형을 먼저 확인하는 습관을 기르자.