[프로그래머스] LV 3 징검다리 건너기

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

프로그래머스

접근방법

1. 건너는 사람은 무한대, 각 돌의 내구도는 1 ~ 2억, 돌 내구도 배열의 크기는 최대 20만
2. 따라서 돌 배열을 순회하며 O(nlogm) 이하의 알고리즘으로 풀이를 해야한다
3. 한명씩 건널때 마다 돌 내구도는 -1이된다
4. 이분탐색으로 1 ~ 2억의 범위에서 적당한 사람 수 를 구하기로한다
5. 먼저 돌 내구도의 max값을 구해 이분 탐색을 구현한다
   1. 건넌사람이 mid 값으로 가정하고 돌 내구도 배열을 순회한다
   2. s-m 값이 0 이하인구간이 k이상 유지된다면 해당 케이스는 건널 수 없는 케이스다
   3. 발견하지 못했다면 건널 수 있는 케이스이다
6. 건널 수 있는 케이스라면 ans와 최대 비교후 갱신한다

코드

import java.util.*;
class Solution {
    int ans = 0;
    public int solution(int[] stones, int k) {
        int max = 0;
        for(int i : stones) max = Math.max(max,i);
        
        bs(max,stones,k);
        return ans+1;
    }
    void bs(int max,int[] stones,int k){
        int l =1;
        int r =max;
        
        while(l <= r){
            int m = (l+r)/2;
            
            if(check(m,stones,k)){
                ans = Math.max(ans,m);
                l = m+1;
            }else{
                r = m-1;
            }
        }
    }
    boolean check(int m, int[] stones,int k){
        int cnt = 0;
        for(int s : stones){
            if(s-m <= 0){
                cnt++;
            }else{
                cnt = 0;
            }
            if(cnt >= k) return false;
        }
        return true;
    }
}