[이분탐색] 프로그래머스 '징검다리 건너기' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드) 완탐. 당연히 타임아웃. 정답도 일부만 맞고..일부는 틀림.

function solution(stones, k) {
    let answer = 1;
    let zero = 0;
    for(let i=0;i<stones.length;i++){
        if(stones[i] === 0) zero ++;
        if(zero === k) answer = 0;
    }
    
    while(true){
        let another = 0;
        let ok = true;
        for(let i=0;i<stones.length;i++){
            if(stones[i] > 0) {
                stones[i] -= 1;
                another = 0;
            }
            if(stones[i] === 0 && another < k) another += 1;
            if(stones[i] === 0 && another === k){
                ok = false;
                break;
            }
        }

        if(ok) answer += 1;
        else break;
    }
    
    return answer;
}

정답) 

function solution(stones, k) {
    let left = 1;
    let right = 200000000;

    while(left <= right) {
        const mid = (left + right) / 2 >> 0;

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

            if(count === k) break;
        }

        if(count === k) right = mid - 1;
        else left = mid + 1;
    }

    return left;
}

내가 했던 방식대로 접근하면 stones의 길의가 최대 20만이고, 각 원소의 최대값은 2억이 되므로 당연히 시간초과가 나게 된다. 

따라서 완탐 방식이 아닌 다른 접근 방식을 생각해야 한다. stones 배열의 각 원소들의 값이 최소 1 이상, 최대 2억 이하라는 말은 징검다리를 건널 수 있는 최소 인원의 값이 최소 1이상, 최대 2억이라는 것이다. 이처럼 정답의 최소값, 최대값이 정해져 있고, 이 사이에서 최적의 답을 찾아야한다면 이분탐색을 생각해야 한다.

초기 left 값은 1, right 값은 2억이 될 것 이다. mid 값은 (left + right) / 2 값이 된다. 이때 소수점 이하는 버려주는 처리를 해야 한다. mid 값은 돌을 건너갈 수 있는 최대 니니즈 친구들의 명수다. 해당 친구들이 모두 돌을 건너가기 위해서는 0이 되는 돌이 k번 연속되지 않아야 한다. 따라서 mid 값을 stones 배열의 각 원소에서 빼고 난 뒤의 결과값이 0보다 작거나 같은 경우가 k 번 연속되는 경우, 해당 mid 값은 정답이 아니다.

만약 0이 되는 돌이 k번 연속되는 경우라면 그 mid 값은 정답이 아니라는 의미로 최대값의 범위를 mid 값 보다 작게 설정하여야 하므로 right 값을 mid - 1을, 만약 k번 보다 돌의 개수가 작다면 그 mid 값보다 큰 값이 정답이 될 수도 있다는 의미이므로 left = mid + 1 을 해준다.

left가 right 와 같은 값이 되었을 때에도 최대 인원을 구해주어야 하기 때문에 left가 right 보다 작거나 같을 때까진 이분탐색을 반복하도록 한다.

이때 정답으로 리턴해주어야 하는 값은 left가 된다. right 값은 계속 큰 값에서 작은 값으로 줄어드는 값이고, left 값은 작은 값에서 큰 값으로 늘어나는 값이므로 left 변수에 건널 수 있는 최대 인원이 담기게 되기 때문이다.

 

이해에 참고한 블로그)

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%EA%B1%B4%EB%84%88%EA%B8%B0-JS

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

 

설명이 자세하게 되어 있는 블로그가 있어 다행이다. 앞으로 투포인터, dp, 이분탐색 문제를 많이 연습해야겠다. ㅠㅠ

 

복기

7/3