[프로그래머스] 징검다리 건너기 Java 풀이 및 해설

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

프로그래머스

풀이 방법

0명부터 200000000명을 이분탐색을 통해 n명이 이 다리를 건널 수 있는지 탐색하면 된다.

 

어떻게 풀지 전혀 모르겠는데 검색해보고 이렇게 이분탐색을 사용해서 문제를 푸는구나 신기했다...

 

전체 코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        int start = 0;
        int end = 200000000;
        
        while(start<=end) {
            int mid = (start + end) / 2;
            if(isAble(stones, k, mid)) {
                answer = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        return answer;
    }
    
    // stones를 n명이 건널 수 있는가
    boolean isAble(int[] stones, int k, int n) {
        
        int cnt = 0;
        for(int i=0; i<stones.length; i++) {
            if(stones[i] < n)
                cnt++;
            else
                cnt=0;
            
            if(cnt==k)
                return false;
        }
        return true;
    }
}