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

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

문제 풀이

그냥 일반적인 방법으로 2중 for문을 써가며 풀면 시간초과가 뜬다. 그래서 이분탐색으로 풀어야한다.

left는 가장 작은 값인 1로 두고 right은 문제에서 주어진 가장 큰 값인 200000000로 하였다.

checkStone이라는 함수를 만들어 건너갈 수 있는지 없는지를 체크하였다.
넘어 갈 수 있는 경우에는 넘어 갈 수 있는 경우의 가장 작은 값인 mid 값으로 설정,
right의 경우에도 넘어갈 수 없으니깐.. 못 넘어가는 것의 가장 작은 값인 mid 값으로 설정.
조건은 left < right -1 일 때까지로 했다. left와 right가 같은 경우에도 끝나야 하기 때문이다.

function checkStone(stones, mid, k) {
    let now = 0; // 몇개가 연속으로 0 미만이 되었는지
    for(let i = 0; i < stones.length; i++) {
        if(stones[i] < mid) { // mid가 더 크면 stones[i] - mid 가 0보다 작다는 소리다. 그러면 마지막 사람이 지나가기 전에 돌이 0이 됐다는 소리다.
          // 만약 딱 0이라면 자신이 지나가고 나서 0이 되므로 지나갈 수 있다는 소리.
            now += 1;
        }
        else { // 지나갈 수 있을 땐 연속으로 못 지나가는게 초기화 됨.
            now = 0;
        }
        if(now >= k) { // 연속으로 못 지나가는 개수가 k보다 크거나 같으면 통과 못 하는 것.
            return false;
        } 
    } 
    
    return true;
}
function solution(stones, k) {
    let left = 1; // 최소, 최대값
    let right = 200000000;

    while(left < right-1) {
        let mid = parseInt((left + right) / 2);
        if (checkStone(stones, mid, k)) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left;
}