[JS/Programmers] 64062. 징검다리 건너기

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64062

❗️접근방법

윈도우 슬라이딩, 이분탐색

👆 1차 코드(정확성 ✅ 효율성 ❌)

class Queue {
	constructor(){
		this.storage = {};
		this.front = 0;
		this.rear = 0;
	}

	size() {
		if (this.storage[this.rear] === undefined) return 0;
		else return this.rear - this.front + 1;
	}

	add(value) {
		if (this.size() === 0){
			this.storage['0'] = value;
		} else {
			this.rear += 1;
			this.storage[this.rear] = value;
		}
	}
		
	popleft() {
		let temp;
		if(this.size() === 0) temp = undefined;
		else if (this.front === this.rear) {
			temp = this.storage[this.front];
			delete this.storage[this.front];
			this.front = 0;
			this.rear = 0;
		} else{
			temp = this.storage[this.front];
			delete this.storage[this.front];
			this.front += 1;
		}
		return temp;
	}
}

function solution(stones, k) {
    const window = new Queue();
    let maxValue = 0;
    
    for (let i = 0; i < k; i+=1){
        window.add(stones[i]);
        maxValue = stones[i] > maxValue ? stones[i] : maxValue;
    }
    let minOfMax = maxValue;
    
    for (let i = k; i < stones.length; i+=1){
        const tmp = window.popleft();
        window.add(stones[i])
        // console.log(Object.values(window.storage))
        if(tmp === maxValue){
            maxValue = Math.max(...Object.values(window.storage));
            minOfMax = minOfMax > maxValue ? maxValue : minOfMax;
        }else if(stones[i] > maxValue){
            maxValue = stones[i];
            minOfMax = minOfMax > maxValue ? maxValue : minOfMax;
        }
    }
    return minOfMax;
    
}

maximum sliding window
징검다리를 최대 간격으로 뛰면 한 스텝에 k만큼 뛸 수 있다.
즉, 크기가 k인 윈도우를 슬라이딩하며 각 윈도우마다 최댓값(maxValue)을 기록한다.
그리고 그 최댓값들 중 최솟값(minOfMax)이 정답이다.
한 칸씩 윈도우를 오른쪽으로 움직이면서 제일 왼쪽에 있던 원소가 queue에서 popleft 된다.
이 원소가 직전 maxValue라면 maxValue를 갱신하기 위해 현재의 윈도우 내에서 최댓값을 찾는다.

시간초과 원인
O(stones.length) 으로 풀어야 통과하는 문제이다.
위의 풀이에서는 for 문 내에서 배열의 최댓값을 구하기 위해 Math.max를 사용하므로 O(N^2)만큼의 시간이 든다.

✌️ 2차 코드(통과✅ - 다른 사람 풀이 참고)

function BinarySearch(stones, k, min, max){
    if (min === max) return min;
    const mid = ((min + max)/2) >> 0;
    let cnt = 0;
    for (let i = 0; i < stones.length; i+=1){
        if(cnt === k) break;
        if (stones[i] - mid <= 0) cnt += 1;
        else cnt = 0;
    }
    if (cnt === k){
        return BinarySearch(stones, k, min, mid);
    }else{
        return BinarySearch(stones, k, mid+1, max);
    }
}

function solution(stones, k) {
    return BinarySearch(stones, k, 1, 200000000);
}

(참고: https://yoon-dumbo.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%EA%B1%B4%EB%84%88%EA%B8%B0-js-%ED%92%80%EC%9D%B4-%EC%9E%88%EC%9D%8C)

이분탐색
문제에서 답은 0~200000000 사이라는 것을 알 수 있다.
(참고한 블로그에 따르면, 최댓값이 1억 이상인 경우 완전 탐색이 아닌 이분탐색으로 답의 범위를 줄여나가는 것이 권장된다고 한다.)
최소값과 최댓값, 그리고 그 중간값(mid)을 갱신하며 (stones의 원소 - mid)<= 0인 개수가 연속으로 k개인지 확인한다.