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

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

코딩테스트 연습 - 징검다리

 

이분 탐색 주제, Level 4 문제이다. distance 가 0 부터 1,000,000,000 까지 있기 때문에 단순 for 루프로 계산할 경우 시간 초과가 발생한다는 것이 문제 힌트로 제시되어 있다.

돌 간의 간격이 가장 작은 순으로 n 개 이하로 추리는 과정까지에서 이분 탐색을 수행하면 정답이 나온다.

 

과정은 다음과 같다.

• rocks 배열 오름차순 정렬
• left = 0, right = distance 설정 후 이분 탐색 수행.
• 단순 이분 탐색이 아니다. 돌과 돌 사이 간격을 mid 값과 비교하면서 mid 값보다 작은 경우에는 일단 제거할 대상으로 count, 그렇지 않으면 이전 돌 위치로 업데이트.
• 제거해야 될 count 가 n 보다 크다면,
  • right = mid - 1;
• 제거해야 될 count 가 n보다 작거나 같다면,
  • left = mid + 1;
  • answer = mid;
• 최종 answer 값 리턴

 

예제 코드는 다음과 같다.

import java.util.*;
class Solution {
    public static int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);

        int left = 0;
        int right = distance;
        while (left <= right) {
            int prev = 0;
            int removeCount = 0;
            int mid = (left + right) / 2;
            for (int i = 0; i < rocks.length; i++) {
                if (removeCount > n) break;
                if (rocks[i] - prev < mid) {
                    removeCount++;
                } else {
                    prev = rocks[i];
                }
            }
            if (removeCount <= n) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
}