프로그래머스 징검다리 건너기

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

처음에는 sliding window방식인가?하고 범위를 늘려나갈 것을 생각했지만, stones배열을 보니 시간초과가 나올 확률이 매우 커보였다.

stones배열을 보니 0이 k값만큼 연달아 나오기 전까지는 계속해서 뺄 수 있겠다라고 생각했고, 최솟값만큼 계속 빼면 어떨까라는 생각을 하였다.
이후에 돌을 최대한 뺄수있는 어떤 값이 존재하고, 그건 최솟값보다는 작고 최댓값보다는 큰데, 두 수 사이에 어떤 지점인데 하나씩 확인하기는 어렵겠다는 생각이 들었다.
그렇기 때문에 이분탐색을 통해 이 지점을 좁혀나가면 좋겠다라는 생각을 하였다.
이분탐색을 통해 해결했는데, 항상 느끼지만 이분탐색 알고리즘 자체는 쉬운데 응용되서 나올때 범위를 잘 맞춰주는게 더 중요하다고 생각한다.
이 문제 또한 단순히 이분탐색을 알고있다고 바로 이분탐색을 떠올리는 것이 어렵다고 생각하고, 이분탐색을 더 깊게 이해하여 이분탐색의 하한선, 상한선이 어디인가를 잘 살펴보고 문제에 적용하는 것이 중요함을 깨달았다.

def solution(stones, k):
    answer = 0
    ## 연속해서 0 이하가 나오는 값이 k이면 종료
    start = 1
    end = 200000000
    while start < end:
        mid = (start + end) // 2
        collapsed = list(map(lambda x: x - mid, stones))
        cnt = 0
        for i in range(len(stones)):
            if collapsed[i] <= 0:
                cnt += 1
            else:
                cnt = 0
            if cnt >= k:
                break
        if cnt >= k:
            end = mid
        elif cnt < k:
            start = mid + 1
    return end