[프로그래머스] Lv3. 징검다리 건너기- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 징검다리 건너기

문제

제한사항

📌 내가 생각한 풀이

연속된 0의 개수를 찾고, 0의 개수가 k면 최대로 건널수 있는 경우이다. 여기서 중요한 것은 시간복잡도를 효율적으로 해야하는 것 인데, 돌의 원소를 기준으로 이분탐색을 하자!

//연속되는 0의 개수가 k개 이상이면 break
// 돌의 원소의 값으로 이진탐색을 하자.
// 최소:1, 최대:20000000

function solution(stones, k) {
    var answer = 0;
    let l = 1
    let r = 200000000;
    while(l <= r){
        let mid = Math.floor((l+r)/2);
        let count = 0;
        for(var i =0; i<stones.length; i++){
            if(stones[i] - mid <= 0) count++;
            else count = 0;
            if(count === k) break;
        }
        if(count === k) r = mid-1;
        else l = mid+1;
        
    }
    return l;
}

📌 느낀점

새로운 방식의 이분탐색이였다. lv2. 피로도 문제를 보면, 라운드를 이분탐색으로 풀었지만, 여기선 돌의 원소의 값을 이분탐색으로 풀어야 하는점이 접근이 어려웠다.