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

😉 아이디어

1. 이진탐색 기반으로 _!1 ~ 200000000!_의 범위 중 얼마나 많은 사람들이 징검다리가 통과가능한지 찾는 문제

😉풀이

def solution(stones, k):
    left, right = 1, 200_000_000
    maxPeople = 0
    
    while left <= right:
        mid = left + (right - left) // 2
        blockedCnt = 0
        for stone in stones:
            # 0보다 작으면 현재 mid 값의 인원보다 적은 사람만 지나가기 가능
            if stone - mid < 0:
                blockedCnt += 1
                if blockedCnt >= k:
                    break
            else:
                blockedCnt = 0
                    
        # 건널 수 없는 돌의 개수 확인
        if blockedCnt >= k:
            # 막힌 돌이 k개 이상이면 실패 right 감소
            right = mid - 1
        else:
            # 건널 수 있는 경우 left 증가 -> 최대 값 검색
            left = mid + 1
            maxPeople = mid
            
    # print(f'최대 인원 : {maxPeople}')
    return maxPeople

✔️링크 : https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=python3