Lv 3. 징검다리 건너기

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

프로그래머스

 

 

이문제는 징검다리를 건널 수 있는 최대 사람 수를 구하는 문제다.

stones 배열은 징검다리의 각 위치가 견딜 수 있는 최대 사람 수를 나타내며,

k는 건널 수 없는 돌의 연속 개수를 의미한다.

이 문제는 이분 탐색을 통해 최적의 값을 찾는 방식으로 풀 수 있다.

사람 수의 범위를 최소 1명부터 최대 징검다리 배열의 최댓값까지로 설정한다.

이분 탐색을 통해 사람 수의 중간값(mid)을 사용해

사람들이 징검다리를 건널 수 있는지 확인한다.

 

find 메서드는 현재 mid 값만큼 사람들이 건널 때 돌이 견딜 수 있는지를 검사한다.

돌이 mid 값보다 작은 경우, 건널 수 없는 돌의 연속된 횟수를 check로 증가시키고,

check가 k보다 커지면 false를 반환해 건너기 불가능하다는 것을 확인하는 메서드다.

반대로, 연속된 건널 수 없는 돌이 k 이하라면 true를 반환해 건널 수 있다고 판단한다.

 

solution 메서드에서는 이분 탐색을 진행하며,

find 메서드의 결과에 따라 start와 end의 범위를 좁혀 나간다.

find가 true를 반환하면 건널 수 있는 사람 수(mid)를 answer로 갱신하고

start를 mid + 1로 이동해 더 큰 값도 가능한지 확인한다. 반면, false일 경우

end를 mid - 1로 줄여 더 적은 인원에 대해 재검토한다.

 

 

import java.util.*;

class Solution {
    private boolean find(int[] stones,int n,int k){
        int check = 0;
        for(int i = 0 ; i < stones.length ; i++){
            if(stones[i] < n) check++;
            else check = 0;
            if(check > k) return false;
        }
        return true;
    }
    public int solution(int[] stones, int k) {
        int answer = 0;
        int start = 1;
        int end = Arrays.stream(stones).max().getAsInt();
        while(start<=end){
            int mid = (start + end) / 2;
            if(find(stones,mid,k-1)){ 
                answer = mid;
                start = mid + 1; 
            }
            else end = mid - 1;
        }
        return answer;
    }
}