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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43236

문제 풀이

• 이분 탐색을 이용하여 풀이하였다.
• 이분 탐색의 대상은 돌 사이의 거리이다.
• 0 ~ distance 사이에서 이분 탐색을 진행하는데 특정 돌 사이의 거리가 주어지면 정렬된 돌 위치 배열을 순회하며 각 돌들에 대해 이전 배치한 돌과의 거리와 비교하며 주어진 돌들을 배치할 수 있는 개수를 구할 수 있다.
• 이렇게 배치할 수 있는 돌의 개수와 (전체 돌 개수 - n)을 비교하여 분기하면 원하는 값을 구할 수 있다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        //돌 사이 간격을 기준으로 이분 탐색 진행
        Arrays.sort(rocks);
        int remain = rocks.length - n;
        int lo = 1;
        int hi = distance + 1;
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            //해당 최소 거리로 배치할 수 있는 돌 개수 카운팅
            int cnt = 0;
            int cur = 0;
            for (int i = 0; i < rocks.length; i++) {
                if (rocks[i] - cur >= mid) {
                    cnt++;
                    cur = rocks[i];
                }

                //마지막 돌일 경우
                if (i == rocks.length - 1) {
                    if (distance - cur < mid)
                        cnt--;
                }
            }

            if (cnt >= remain) lo = mid;
            else hi = mid;
        }
        return lo;
    }
}