[64062] 징검다리 건너기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

문제 해결 방법

이진 탐색으로 최대 몇 명이 건널 수 있는지 검사한다.

 

mid값 수 만큼의 니니즈 친구들이 징검다리를 건넜을 때 더 이상 밟을 수 없는 돌의 개수가 k 개라면 실패.

-> max 값을 줄여준다.

k개 미만이라면 성공.

-> min 값을 늘려준다.

 

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        int min = 1;
        int max = 200000000;
        
        while(min <= max) {
            int mid = (min + max) / 2;
            int cnt = 0;
            for(int i = 0; i < stones.length; i++) {
                if(stones[i] - mid <= 0) cnt++;
                else cnt = 0;
                
                if(cnt == k) break;
            }
            if(cnt == k) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}