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

문제

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

풀이

이분 탐색을 활용하여 푼 풀이

start와 end를 지정한다.

end는 정답이 될 수 있는, 징검다리를 건널 수 있는 최대 인원 수 이다.

is_ok() 함수를 통해서 징검다리를 건널 수 있는지 확인한다.
징검다리 목숨 - 사람 인원 수 가 0 보다 작으면 징검다리는 더 이상 사용할 수 없다는 의미이다.

순차적으로 이를 체크하면서 연속적으로 부서진 징검다리의 개수를 확읺나다.

만약 k 보다 이 값이 작으면 이 인원수(mid)로 징검다리를 건널 수 없다는 의미가 된다.

is_ok() 의 반환값이 True인 경우
범위를 오른쪽으로 옮기고 answer 를 mid + 1 로 할당한다.

is_ok() 의 반환값이 False 인 경우
범위를 왼쪽으로 옮긴다.

def solution(stones, k):
    start = 0
    end = max(stones)
    mid = 0 
    answer = 0 
    while start <= end:
        mid = (start + end) // 2
       
        if is_ok(stones, k, mid):
            start = mid + 1
            answer = mid + 1
        else:
            end = mid - 1
           
    return answer

def is_ok(stones, k, mid):
    result = 0
    continuous = 0
    for stone in stones:
        if stone - mid <= 0:
            continuous += 1
            if continuous > result: 
                result = continuous
        else: 
            continuous = 0

    if result >= k: 
        return False
   
    return True