징검다리 건너기

코드

def solution(stones, k):
    lo = 1
    hi = max(stones)
    while lo < hi:
        mid = (lo + hi) // 2 # mid = 징검다리를 건너는 친구 수

        gap = 0 # 0의 개수
        for i in range(len(stones)):
            if stones[i] - mid <= 0: # 반복문으로 징검다리를 -1 하지 않고 
            # 친구수(mid)만큼 한번에 빼버린다.
                gap += 1
            else:
                gap = 0 # 0이 연속적인 경우에만 고려해야하기 때문에 0으로 초기화
            if gap >= k:
                break

        if gap >= k:
            hi = mid
        else:
            lo = mid + 1 # lower bound
    return lo

참고

접근 방식

이분탐색을 통해 답을 구한다.
단, 미리 답이 정해져있다고 간주하여 풀어야한다.
-> 즉, mid값이 답이라고 정해둔 뒤, 이후에 답(mid) 검증하는 순서