[프로그래머스] 징검다리 건너기 - 자바 Java

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

프로그래머스

 

개념: 이분탐색

 

문제 설명

• 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어든다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없고, 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있다.
• 무조건 가장 가까운 디딤돌로만 건너뛴다.
• 한 번에 한 명씩 징검다리를 건너야 하며, 한 명이 징검다리를 모두 건넌 후에 그 다음 사람이 건너기 시작한다.
• 징검다리를 건너야 하는 사람들의 수는 무제한이라고 간주한다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 `stones`와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 `k`가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

`stones` 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수다.

---

입출력 예시

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

4번째 사람은 다리를 건널 수 없다

---

풀이

• 사람 0번, 1번, 2번, … 이렇게 지나간다고 가정할 때,
  • (디딤돌 수) - (사람 번호) < 0 인 경우가 연속으로 k번 이상이면 못 건넌다
    
    • 가능한 답인 0~200,000,000 중에서 못 건너게 되는 지점을 이분탐색을 통해 찾는다

import java.util.*;

class Solution {
    static int[] Stones;

    public static int binarySearch(int left, int right, int k) {
        if (left <= right) {
            int mid = (left + right) / 2;

            if (checkCross(mid, k)) {
                return binarySearch(mid + 1, right, k);
            } else {
                return binarySearch(left, mid - 1, k);
            }
        }

        return left;
    }

    public static boolean checkCross(int M, int k) {
        int zero = 0;
        for (int i = 0; i < Stones.length; i++) {
            if (Stones[i] - M <= 0) {
                zero++;
                if (zero >= k) {
                    return false;
                }
            } else {
                zero = 0;
            }
        }
        return true;
    }

    public int solution(int[] stones, int k) {
        Stones = stones;
        int answer = binarySearch(0, 200000001, k);
        return answer;
    }
}