[프로그래머스] 징검다리 건너기(64062)

1. 문제 풀이 아이디어

• 이분 탐색을 활용해 중간값을 기준으로 건널 수 있는 사람 수를 계산하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int[] stones, int k) {
        int l = 0, r = 0;
        for (int i : stones) {
            r = Math.max(r, i);
        }
        while (l <= r) {
            int m = (l + r) / 2;
            int count = 0;
            int max = 0;
            for (int i = 0; i < stones.length; i++) {
                if (stones[i] - m <= 0) {
                    count++;
                    max = Math.max(max, count);
                } else {
                    count = 0;
                }
            }
            if (max + 1 > k) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

3. 정리

• 초기 범위를 설정하여 건널 수 있는 사람의 수를 이분 탐색한다.

• 중간값 m에 대해 모든 돌을 순회하면서, 돌의 내구도가 m 이하가 되는 연속 구간의 최대 길이를 계산한다.

• 연속 구간의 최대 길이가 k 이상이면 r = m - 1로 줄이고, 그렇지 않으면 l = m + 1로 늘린다.

• 이분 탐색이 종료된 후, 최종적으로 l 값을 반환하여 최대 건널 수 있는 인원을 결정한다.