징검다리 건너기

• 문제

programmers.co.kr/learn/courses/30/lessons/64062?language=java

• 코드

import java.util.*;

class Solution {
    private boolean canGo(int[] stones, int mid, int k){
        int tmpArr[] = new int[stones.length];
        for(int i=0; i<stones.length; i++){
            tmpArr[i] = stones[i] - mid;
        }
        int count = 0;
        for(int i=0; i<tmpArr.length; i++){
            if(tmpArr[i] > 0){
                count = 0;
            }else{
                count++;
                if(count >= k)
                    return false;
            }
        }
        return true;
    }
    
    public int solution(int[] stones, int k) {
        int answer = 0;
        int end = 1;
        int start = 200000000;
        int mid;
        int maxVal = 0;
        for(int i=0; i<stones.length; i++){
            end = Math.max(end, stones[i]) + 1;
            start = Math.min(start, stones[i]) - 1;
        }
        
        while(start <= end){
            mid = (start + end)/2;
            if(canGo(stones, mid, k)){
                maxVal = Math.max(maxVal, mid);
                start = mid + 1;
            }else{
                end = mid -1;
            }
        }
        
        return maxVal+1;
    }
}

• 피드백
  • 이분탐색을 쓸 때 start < x < end 의 범위에서 탐색한다는 것을 생각하자.
  • 200000000의 큰 수가 나왔다. 그래서 이분탐색을 씀. 큰 수가 나오면 이분탐색을 먼저 생각하자.