⁉️문제

https://programmers.co.kr/learn/courses/30/lessons/64062
숫자가 적혀있는 징검다리가 있다.
이 징검다리의 숫자는 사람이 건널때마다 1씩 줄어든다.
그리고 0이된다면 그다음 0이아닌 쪽으로 건너뛰어야 한다.
마지막으로 한번에 건너뛸 수 있는 수는 제한되어있다.
이 때, 최대로 건널 수 있는 사람의 수를 구하는 문제다.

예를들면 1 2 3 2 라는 징검다리가 있고, 최대로 2칸을 뛸 수 있다 해보자.
첫번째 사람이 지나가면 징검다리의 숫자는 0 1 2 1이 된다.
두번째 사람 지나간후 -> 0 0 1 0
세번째 사람이 지나가려는데 앞에 0이 두개 있기때문에 못지나간다.
1 2 3 2 징검다리는 최대 2명의 사람이 지나갈 수 있다.

입력: [ stones, k ]

• stones: 1이상 200,000 이하의 배열길이를 갖는다.
  • 각 원소의 값은 1 이상 200,000,000 이하의 값을 가진다.
• k: 1이상 stones의 배열길이 이하의 자연수

출력: 최대로 건널수 있는 사람의 수를 출력한다.

풀이

이 문제는 한번도 풀어보지 않은 유형이라 푸는데 시간이 꽤 많이 걸렸다.
결론부터 먼저 말하면 이진탐색을 사용해 푸는 문제다.

1. 그냥 풀어보기

처음에는 어떤 문제인지 대충 가늠해보려고 완전탐색을 했다.
사람이 한명 건널 때 마다 모든 stones의 값을 1 빼주는 방식이다.

function solution(stones=[], k) {
    let isRunning = true;
    let zeroCnt = 0;
    let people = 1;

    while(isRunning) {
        zeroCnt = 0;
        for (let i=0; i<stones.length; i++) {
            stones[i] -= 1;
            if (stones[i] <= 0) {
                zeroCnt++;
            }else {
                zeroCnt = 0;
            }

            if (zeroCnt === k) {
                isRunning = false;
                break;
            }
            // 만약 끝까지 도달했으면 사람 한명 건널수있음
            if (i === stones.length - 1 && zeroCnt < k) {
                people++;
            }
        }
    }
    return people;
}

이렇게 하면 최악의 경우 stones의 길이가 20만, 모든 원소의 값이 2억이라면
40,000,000,000,000번, 40조번을 순환해야 한다. 무조건 안된다
이 문제가 어떤 문제인지 더 생각을 해봐야 할것같다.

2. 문제이해

정확히 어떤 상황에서 못건너는지 파악하기위해 문제의 예제를 살펴봤다.

stones: 2 4 5 3 2 1 4 2 5 1 , k = 3
첫번째 사람이 건너간 후 👉 1 3 4 2 1 0 3 1 4 1
두번째 사람이 건너간 후 👉 0 2 3 1 0 0 2 0 3 0
세번째 사람이 건너간 후 👉 0 1 2 0 0 0 1 0 2 0
네번째 사람이 건너려고 봤더니 4칸을 뛰어야해서 더이상 진행되지 않는다.

세번째 사람이 건너간후 다리의 상황을 보면 0이 k개만큼 있는걸 알 수 있었다.
바로 여기에!!! 0 1 2 0 0 0 1 0 2 0

배열을 k개씩 보면서 0이 제일 빨리 되는 구간을 찾으면 되겠다는걸 알았다.
이제 예제의 배열을 k개씩 잘라서 해당 구간에서 가장 큰 값을 찾으면 된다.
가장 큰 값만큼 사람이 지나가면 해당 구간은 전부 0이 되기 때문이다.

이제 위의 배열을 자르고 가장 큰 값을 구해본다.

• 2 4 5 -> 5
• 4 5 3 -> 5
• 5 3 2 -> 5
• 3 2 1 -> 3
• 2 1 4 -> 4
• 1 4 2 -> 5
• 4 2 5 -> 5
• 2 5 1 -> 5

stones배열을 k개씩 자르니 8개의 구간이 나왔다.
위에서 구한 가장 큰 값중 작은값이 정답이 된다.

Why❓ 위의경우 3인데 3명이 지나가면 더이상 진행하지 못하기 때문이다.
그리고 위에서 구한 큰값은 몇명이 지나가면 해당 구간이 0이되는지를 구한 값이다.

function solution(stones, k) {
    let result = Infinity;
    for (let i=0; i <= stones.length - k; i++) {
        const max = Math.max(...stones.slice(i, i+k));
        result = Math.min(result, max);
    }
    return result;
} 

위의 논리를 토대로 구현해봤더니 순환횟수가 조금 줄여졌다.
하지만 시간복잡도는 여전히 O($n^2$) 이다.
결국 이것도 안된다. 그럼 어떻게 해야할까?
위에서 구하려고 한것의 정체를 뭔지 다시한번 생각해봤다.

원래 구하려고 한것은 사람이 몇명 지날 수 있는지 구하는거였다.
그렇다. 나는 처음부터 답을 알고있었다.

3. 다시 처음으로 돌아가서

처음에는 1명씩 다리를 건너며 몇명이 지나갈 수 있는지 파악하려했다.
그럴경우 최악의경우 40,000,000,000,000번을 순환해야한다.40조다 40조!!
그래서 뭐가 있을까 생각해보니 예전에 배웠던 이진탐색이 떠올랐다.

만약 이진탐색을 적용한다면 시간복잡도는 O($n^2$)에서 O($nlogn$)으로 훨씬 빨라진다.
방법도더 간단하다. 그냥 이진탐색으로 1~20만중 건널 수 있는 인원 수의 최대를 구하면 된다.

📌 알고리즘

1. mid값으로 다리를 건널 수 있는지 확인한다.
   1-1. 건널 수 있다면 left = mid
   1-2. 건널 수 없다면 right = mid
2. left < right -1일 때까지 1.을 반복한다.

위의 1-1 건널 수 있는 경우 left=mid를 한 이유는
만약 건널 수 있다면 그 숫자를 포함해 작은 값들은 모두 건널 수 있기 때문이다.
그래서 그보다 큰 값도 건널 수 있는지 확인해준 것이다.

1-2에서 건널 수 없는경우 right = mid를 한 이유는
만약 건널 수 없다면 그 숫자를 포함해 큰 값들은 모두 건널 수 없기 때문이다.
그래서 그보다 작은 값은 건널 수 있는지 확인해준다.

left < right-1일때만 while문이 돌아가는 이유는
마지막까지 탐색을 하고 left, right가 1밖에 차이나지 않을때가 탐색의 끝이기 때문이다.

📍 마지막 풀이

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

    function canCross(mid) {
        let zeroCnt = 0;
        for (let i=0; i < stones.length; i++) {
            if (stones[i] < mid) zeroCnt++;
            else zeroCnt = 0;
            if (zeroCnt >= k) 
                return false;
        }
        return true;
    }
    
    while(left < right-1) {
        const mid = parseInt((left + right) / 2); 
        if (canCross(mid)) left = mid;
        else right = mid;
    }
    return left;    
}

canCross() 함수는 건널 수 있는지 판별해주는 함수이다.
0의 개수가 k개 이상이면 건너지 못하므로 false를, 반대의경우 true를 반환해준다.
이진탐색으로 사람의 수를 탐색하며 해당 인원이 건널 수 있는지 확인하는 식이다.