[프로그래머스] 징검다리 건너기 (Python)

Link

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

My Solution (Failed)

def solution(stones, k):
    n = len(stones)
    max_list = [0] * n
    for i in range(n):
        for j in range(i, min(i + k, n)):
            max_list[j] = max(max_list[j], stones[i])
        if i >= k - 1:
            answer = min(answer, max_list[i])
    return answer

내심 기대했지만 역시나 시간 초과가 떴다. O(n * k)의 복잡도니까 최악의 경우 200000^2 번 정도의 연산이 수행됐을 것이다.

이분 탐색을 이용한 풀이

def solution(stones, k):
    left = 1
    right = 200000000
    
    while left <= right:
        mid = (left + right) // 2
        stones_copy = stones[:]
        
        max_gap = 0
        curr_gap = 0
        for i in range(len(stones_copy)):
            stones_copy[i] -= mid
            if stones_copy[i] <= 0:
                curr_gap += 1
                max_gap = max(max_gap, curr_gap)
            else:
                curr_gap = 0
        
        if max_gap >= k:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

left=1, right=200,000,000 으로 두고 이분 탐색을 수행하면 시간제한 내에 풀 수 있다.