[틀림] 프로그래머스 징검다리 건너기 // 매개변수 탐색

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=java#

프로그래머스

* 시도1

1명씩 보내보면서 (무한대)

20만의 배열을 돌면서

연속된 0의 갯수가 k 이상이면 불가능

 

* 풀이

한명씩 보내보는대신,

x명일때 가능한가?를 탐색

 

go함수 구현 시도1

한명씩 보내는대신, x와 arr의 차이를 구해보면 됨

이게 음수이면, 갈수없는곳임.

(한번에 이 발상을 하기가 좀 빡세긴 함...)

//x명이 건널수있는가
    boolean go2(int x){
        int cnt=0;
        for(int i=0;i<arr.length;++i){
            if(cnt>=k){
                return false;
            }
            if(arr[i]-x < 0){
                cnt++;
                continue;
            }
            cnt=0;
        }
        return true;
        // return cnt<k
    }

문제점 : 마지막에 몰려있는경우, 체크가안됨.

return cnt<k로 바꿔야함.

go함수 구현2

boolean go(int x){
        int cnt=0;
        for(int i=0;i<arr.length;++i){
            if(arr[i]-x < 0){
                cnt++;
                if(cnt>=k){
                    return false;
                }
            } else {
                cnt=0;
            }
        }
        return true;
    }

음수가 나오면, 그때그때, 판단하는 방법

마지막에 몰려있는 경우도 커버가능