[JAVA] 프로그래머스 LEVEL3 징검다리 건너기

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

프로그래머스

코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 > 징검다리 건너기

 

난이도: LEVEL3

알고리즘 유형:  이분탐색 (매개변수 탐색)

풀이 설명

전형적인 이분 탐색 문제이다.

징검다리를 건너는 게 가능한 니니즈 친구들의 최대 수를 구한다. 

 

이분 탐색 시작 조건 

start = 0

end  = 200,000,000 

모든 징검 다리가 end와 동일하면 최대 200,000,000 만큼 징검다리를 건널 수 있다. 

 

calculate API

public static boolean calculate(int [] stones, int k, int mid){
    int cnt = 0;
    for(int i = 0; i < stones.length; i++){
        if(stones[i] - mid <= 0){
            cnt++;
        }
        else cnt = 0;
        if(cnt == k){
            return false;
        }
    }
    return true;
}

현재의 인원이 징검다리를 건널 수 있는지 확인하는 메소드이다. 

가능 여부에 따라서 boolean 값을 반환한다. 

 

cnt의 의미는 건너지 못하는 징검다리의 연속된 개수이다. 

cnt == k 라면 

현재 인원으로는 징검다리를 건너지 못한다. 

 

이분 탐색 

while(start < end){
    int mid = (start + end) / 2;
    boolean result = calculate(stones, k, mid);
    if(result){
        start = mid + 1;
    }
    else end = mid;
}
return start;

 

이분 탐색 코드이다. 

caluculate 계산 결과가 true면 현재 범위보다 더 증가된 범위를 탐색하기 위해서 start를 mid + 1한다.

그럼 탐색 범위는 start + 1에서 end까지 

만약 결과가 false라면 탐색 범위를 start에서 mid까지 줄인다.

정답 코드 

class Solution {
    public int solution(int[] stones, int k) {
        int start = 0;
        int end   = 200000000;
        while(start < end){
            int mid = (start + end) / 2;
            boolean result = calculate(stones, k, mid);
            if(result){
                start = mid + 1;
            }
            else end = mid;
        }
        return start;
    }
    public static boolean calculate(int [] stones, int k, int mid){
        int cnt = 0;
        for(int i = 0; i < stones.length; i++){
            if(stones[i] - mid <= 0){
                cnt++;
            }
            else cnt = 0;
            if(cnt == k){
                return false;
            }
        }
        return true;
    }
}