1. 문제 설명

징검다리 건너기

2. 문제 분석

한 번씩 건널 때마다 바위 내구도가 1씩 감소하고, 연속된 k개의 바위의 내구도가 0일 때 바위를 건널 수 없다. 이때 바위를 건넌 총 사람 수를 구하는 문제이다. x명이 연속으로 건널 때 k개의 연속된 단위에서 연속으로 0 이하가 발생하는지 확인하는 문제이다. 효율성을 위해 'x'명을 구하는 것은 이분 탐색으로, k개의 연속된 단위를 검사하는 과정은 완전 탐색으로 풀 수 있다.

1. 바위 내구도의 최솟값과 최댓값 사이에서 '몇 명' x명이 건널 수 있는지 결정한다.
2. x명이 건널 때 k개의 연속된 바위가 k개 이상의 내구도를 가지고 있는지 확인한다.
3. x명의 최댓값을 return한다.

• 특정 바위가 x 미만일 때(즉 이 바위는 x번까지 밟을 수 있다) zero_cnt를 증가시켜주는데, '연속된 바위들'에서만 다루어야 하기 때문에 그렇지 않으면 다시 0으로 만든다. k가 되는 그 시점에서 x명이 '건널 수 없는' 상황이므로 jumpable==False를 return. 모든 상황에서 건널 수 있으면 jumpable=True를 return.

3. 나의 풀이

def solution(stones, k):
    left, right = 0, max(stones)
    # 징검다리를 밟을 수 있는 최대값과 최솟값 사이에서 건널 수 있는 사람 수가 결정된다
    result = 0

    def jumpable(mid):
        # 연속된 k개의 다리를 건넌다. 
        zero_cnt = 0
        for stone in stones:
            if stone < mid:
                zero_cnt += 1
                if zero_cnt == k: return False
                # 특정 다리가 '사람 수'보다 작으면 건너는 도중 0이 된다. 
                # k개 이상 0이 연속으로 나오면 건널 수 없다는 뜻이다.
            else: zero_cnt = 0
        return True

    while left <= right:
        # 최솟값-최댓값 사이에서 건널 수 있는 사람 수를 빠르게 찾는 이분 탐색.
        mid = (left + right) // 2
        if jumpable(mid):
            result = max(result, mid)
            left = mid + 1
        else: right = mid - 1
    
    return result