[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

문제

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

프로그래머스

 

소스코드

import java.util.Arrays;

public class Solution {

    public int solution(int[] stones, int k) {

        int answer = 0;
        int start = Arrays.stream(stones).min().getAsInt();
        int end = Arrays.stream(stones).max().getAsInt();

        while(start <= end) {

            int mid = (start + end) / 2;

            if(cross(mid, stones.clone(), k)) {
                answer = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }

        }

        return answer;
    }

    public boolean cross(int num, int[] stones, int k) {

        Arrays.setAll(stones, i -> (stones[i] - num + 1)); // --- (1)

        int max = 0, cnt = 0;

        for(int stone : stones) {
            if(cnt > 0 && stone > 0) {
                max = Math.max(max, cnt);
                cnt = 0;
            } else if(stone <= 0) {
                cnt++;
            }
        }

        return Math.max(max, cnt) < k;
    }

}

 

회고

-  이분탐색으로 건널 수 있는 최대 학생 수를 찾아간다.

- cross에서는 num번째 학생이 건널 수 있는지만 판단하면 되기 때문에, (1)에서는 (num-1)번째 학생까지 건넜을 때        stone들의 상태를 만들어준다.

- 이후 num번째 학생이 건널 수 있는지 확인해준다.