[프로그래머스]징검다리 건너기 (JS)

문제

[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기
[링크]https://programmers.co.kr/learn/courses/30/lessons/64062

문제풀이

처음 문제를 보고서 배열크기(2십만),배열원소(2억)에 겁을 먹고 시간복잡도 N으로 풀 수 있는 공식(?)을 찾아보려 고민하였는데, 쉽지 않았다.
그런데 답의 최대값인 배열원소(2억)의 로그2 값이 계산해보니 27.57 밖에 안되더라.. 이분 탐색으로 푸는 문제인 것을 대놓고 제한사항에 적어준 것이었다.
이분탐색으로 정답을 정하고 그 값이 조건에 부합하는지 체크해주면 해결.

코드

function solution(stones, k) {
    let max=0,min=Infinity,answer=1;
    for(let i=0;i<stones.length;i++)max=Math.max(max,stones[i]),min=Math.min(min,stones[i]);
    if(max===min)return max;
    while(min<=max){
        const mid = Math.floor((max+min)/2);
        const temp = [...stones];
        let count=0;
        for(let i=0;i<temp.length;i++){
            temp[i]-mid>=0?count=0:count++;
            if(count>=k){
                max=mid-1;
                break;
            }
        }
        if(count<k)answer=Math.max(answer,mid),min=mid+1;
    }
    return answer;
}