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

1. 문제

프로그래머스

 

[문제 요약]

• 최소 몇 명이 건널 수 있는지 구하기
• 숫자가 적힌 배열, 건널 수 있는 길이
• 숫자의 범위가 크다 (원소의 값이 최대 2억)

 

2. 생각대로 풀기

숫자의 범위가 크기 때문에 무작정 반복문을 돌리면 안된다.
N명이 건널 수 없다면, N보다 큰 수의 사람들도 건널 수 없음.
N명이 건널 수 있다면, N보다 작은 수의 사람들도 건널 수 있음.
-> 이진탐색으로 좁혀가면서 N찾기

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int left = 1;
        int right = 200000000;
        
        // 이진탐색
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (canCross(stones, k, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;
    }
    
    private boolean canCross(int[] stones, int k, int people) {
        int count = 0;
        
        // 각 돌을 건널 때 people만큼의 인원이 지나갈 수 있는지 확인
        for (int stone : stones) {
            
            // 건널 수 없으면 카운트 증가
            if (stone - people < 0) {
                count++;
            } else {
                count = 0;
            }
            
            // 연속된 건널 수 없는 돌의 갯수가 k(길이) 이상이면 false
            if (count >= k) {
                return false;
            }
        }
        
        return true;
    }
}