Solution.java

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance / (rocks.length - n + 1);
        int mid;
        
        while (left <= right) {
            mid = (left + right) / 2;
            
            int[] dist = new int[2];   // dist[0]: 왼쪽 거리, dist[1]: 오른쪽 거리
            int tmp = 0;
            for (int i = 0; i < rocks.length; i++) {
                dist[0] += (i == 0) ? rocks[i] : rocks[i] - rocks[i - 1];
                dist[1] = (i == rocks.length - 1) ? distance - rocks[i] : rocks[i + 1] - rocks[i];
                
                if (dist[0] < mid) {
                    tmp++;
                }
                else {
                    dist[0] = 0;
                }
            }
            if (dist[0] == 0) {
                if (dist[1] < mid) tmp++;
            }
            else {
                if (dist[0] + dist[1] < mid) tmp++;
            }
            
            if (tmp <= n) {
                answer = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
}

다른 분의 글을 참고해 힌트를 얻어 겨우 풀었다..

다음에 이런 문제를 본다면 이분탐색을 생각할 수 있을지 모르겠다.

이분탐색을 이런식으로도 사용하는구나 배울 수 있었던 문제였다.

통과하고 다른 사람의 풀이를 보니 마지막 돌 ~ 도착지점의 거리를 고려를 안 한 코드도 통과되고 있었다.

테스트 케이스가 좀 부족한것같다.

다른 사람의 풀이를 보니 좀 더 깔끔한 방식으로 거리를 비교한 코드가 있던데 다음에 고쳐봐야겠다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges