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

문제 보기

사용한 것

• 최대 건널 수 있는 친구들의 수를 구하기 위한 upper bound

풀이 방법

• l은 1부터, r은 200,000,001부터 upper bound를 구해준다.
  • 징검다리 돌 하나 값의 최대가 200,000,000이므로 최대 200,000,000의 친구들이 건널 수 있기 때문에 r을 200,000,001로 잡아줌
• 'num만큼의 친구들이 건널 수 있는가?'는 'num - 1만큼의 친구들이 건넌 뒤 마지막 친구가 건널 수 있는가?'와 같다.
• stones를 돌면서 num - 1만큼 뺀 값이 0이거나 음수이면 ct를 증가 시킨다. (만약 양수면 ct를 0으로 초기화)
• ct가 k와 같아지면 건널 수 없다는 것이므로 false를 반환한다.

코드

class Solution {

    int[] stones;
    int k;

    public int solution(int[] stones, int k) {
        this.stones = stones;
        this.k = k;

        int l = 1;
        int r = 200_000_001;
        while (l < r) {
            int m = (l + r) / 2;
            if (isPossible(m)) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        return r - 1;
    }

    boolean isPossible(int num) {
        int ct = 0;
        for (int i = 0; i < stones.length; i++) {
            if (stones[i] - (num - 1) > 0) {
                ct = 0;
            } else {
                ct++;
            }

            if (ct == k) {
                return false;
            }
        }

        return true;
    }
}