(javascript) 징검다리 건너기

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

프로그래머스

 

효율성 검사가 있는 문제다

 

 친구들이 하나씩 다리를 건너면서 stones의 값을 하나씩 줄인다면 답은 구할 수 있겠지만 당연히 너무 오랜 시간이 걸릴 것이다.

 시간복잡도는 stones의 길이가 n, stones의 각 값의 최대값이 m일 때, O(n*stones*k)가 될 것이다.

 

 대신 답으로부터 역으로 계산해서, 만약 n명의 친구들이 다리를 건널 수 있다고 가정한다면, 써있는 숫자가 n보다 작은 다리가 k번 이상 연속될 경우 이 가정은 틀렸다고 생각할 수 있다.

 

 n을 1부터 200,000까지 증가시키면서 위의 방법을 적용해보면 n을 찾을 수 있다.

 

 그러나 이 방법도 O(n*m*k)로 충분히 빠르게 계산할 수 없다.

 

 이분 탐색 방식을 적용해서 시간을 줄일 수 있다.

 기본적으로는 위에서 설명한 방식과 똑같다. 하지만 n을 1부터 200,000까지 하나씩 증가시키는 대신, 이분 탐색을 적용하는 것이다.

 min = 0, max = 200,000이라고 하자. mid = (max + min) / 2이다.

 n = mid일 때 다리를 건널 수 있다면 min = mid + 1로 바꾸고 다시 계산해본다.

 반대로 다리를 건널 수 없다면 max = mid로 바꾸고 다시 계산한다.

 

 이렇게 하면 시간복잡도에서 m을 logm까지 줄일 수 있다.

 

코드

function solution(stones, k) {
    var max = stones.reduce((a, b) => Math.max(a, b));
    var min = 0;
    var mid = Math.floor((min + max) / 2);

    while (min < max) {
        // 검사
        var count = 0;
        var pass = true;
        for (var i = 0; i < stones.length; i++) {
            if (stones[i] <= mid) {
                count++;
                if (count === k) {
                    pass = false;
                    break;
                }
            } else {
                count = 0;
            }
        }
        if (pass) {
            min = mid + 1;
            // 건널 수 있음
        } else {
            max = mid;
            // 건널 수 없음
        }
        var mid = Math.floor((min + max) / 2);
    }
    return mid;
}