문제 링크

프로그래머스 문제

풀이

입력값으로 주어지는 stone의 크기가 굉장히 크므로 완전탐색은 불가능하다.
따라서 완전탐색이 아닌 다른 알고리즘을 찾아야만 한다.

제대로 해결하지 못해서 서칭해본결과 이분탐색방법을 통해서 해결해야 하는것을 알수 있었다.

코드

const solution = (stones, k) => {
    let front = 0;
    let back = 200000000;

    while(front <= back){
        const mid = Math.floor((front + back) / 2);

        if(binarySearch(stones, mid, k)){
            back = mid - 1;
        } else{
            front = mid + 1; // front는 구간이 시작되는 위치이다. 
        }
    }

    return front;
}

function binarySearch  (stones, mid, k){
    let count = 0;

    for(let i = 0; i < stones.length; i++){
        if(stones[i] - mid <= 0){
            count++;
        } else{
            count = 0;
        }

        if(count >= k){
            return true;
        }
    }

    return false;
}