[JAVA/이분탐색] 프로그래머스 징검다리 건너기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=java# 

프로그래머스

 

2. 풀이

• 이분탐색을 이용해서 강을 건널 수 있는 최대 사용자 수를 구한다.
• 적힌 숫자가 0인 디딤돌이 K개 이상이 되면 점프해서 건널 수 없다.
  • 즉, 돌에 적힌 숫자 < 건널 사람 수가 K 번 이어지면 점프해서 건널 수 없는 것이다.
  • 이를 이용해 강을 건널 수 있을 지 없는지 판단하여 이분탐색을 진행한다.

 

3. 코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        int start = 1;
        int end = 200000001;
        
        while(start <= end){
            int mid = (start + end) / 2;

            if(canCrossRiver(stones, k, mid)){
                start = mid + 1;
                answer = Math.max(answer, mid);
            }else{
                end = mid - 1;
            }
        }
        
        return answer;
    }
    
    // people명의 사람이 왔을 때 건널 수 있는지
    private boolean canCrossRiver(int[] stones, int k, int people){
        
        int passCnt = 0; // 건널 수 없는 디딤돌 개수
        
        for(int i = 0; i < stones.length; i++){
            if(stones[i] - people < 0) { // 건널 수 없는 돌의 경우
                passCnt++;
            }else{ // 건널 수 있는 돌의 경우
                passCnt = 0; // 이 지점부터 다시 시작할 수 있으므로 0으로 다시 돌림
            }
            
            if(passCnt == k) return false; // k번 건너뛰는 것은 불가능 하므로 건너기 불가
        }
        
        return true;
    }
    
}