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

18 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(stones, k):
    start = min(stones)
    end = max(stones)

    while start <= end:
        cnt = 0
        mid = (start + end) // 2

        for stone in stones:
            if stone - mid <= 0:
                cnt += 1
            else:
                cnt = 0

            if cnt >= k:
                break
        if cnt >= k:
            end = mid - 1
        else:
            start = mid + 1

    return start

범위가 1천만, 1억을 넘어가면 바로 이분 탐색으로 생각해야 한다.