[pro] 프로그래머스 level3 64062 징검다리 건너기 (Java) - 이분탐색

[문제]

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

프로그래머스

 

[풀이]

징검다리를 건널 수 있는 친구들의 수를 기준으로 이분탐색을 한다.

건널 수 있다면 친구들의 수를 늘리기 위해서 left값을 mid+1로 갱신하고, 건널 수 없다면 친구들의 수를 줄이기 위해서 right값을 mid-1로 한다. 

 

징검다리에 써져있는 숫자보다 친구들의 수가 더 많을 경우 숫자가 0보다 작아져 건널 수 없으므로 skip을 증가시키고, 연속된 skip이 k와 같아지면 건널 수 없으므로 false를 반환한다.

 

[코드]

 

class Pro_level3_64062 {
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        //최대 몇 명까지 징검다리를 건널 수 있는지 - 이분탐색
        int left = 1; //건널 수 있는 친구들의 수
        int right = 200000000; 
        
        while(left<=right){
            int mid = (left+right)/2;
            
            //건널 수 없다면 친구들의 수 감소
            if(!check(stones, k, mid)){
                right = mid - 1;
            } else{ //건널 수 있다면 
                left = mid + 1;
                answer = Math.max(answer, mid);
            }
        }
        
        return answer;
    }
    
    //friends명의 친구들이 건널 수 있는지
    boolean check(int[] stones, int k, int friends){
        int skip = 0;
        for(int stone : stones){
            if(stone < friends){
                skip++; //건널 수 없음
            }
            else{
                skip = 0; //건널 수 있음
            }
            
            if(skip==k){
                return false;
            }
        }

        return true;
    }
}