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

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

프로그래머스

 

🤔 문제분석

n명의 사람이 징검다리를 건널때, 최대 몇명이 건널 수 있는지 찾는 문제로 사람의 명수를 기준으로 이분탐색 정답을 찾아냈습니다.

1. start = 0, end = 200000001 ( 징검다리가 버틸 수 있는 최대 크기 200000000)
2. mid 값을 기준으로 징검다리를 건널 수 있는지 없는지 확인하는데, 연속적으로 k개의 다리를 띄어 넘을 수 없다면 건널 수 없다.
3. 건널 수 있냐 (?) 건널수 없냐(?) 의 조건에 따라서 start와 end 값을 지정해준다.
   1. 건널 수 있다면 사람의 명수를 늘려본다.
   2. 건널 수 없다면 사람의 명수를 줄인다.

💻 코드

def solution(stones, k):
    start = 0
    end = 200000001
    answer = -1
    n = len(stones)
    while end >= start:
        mid = (start + end) // 2
        cnt = 0
        can_go = True
        for i in range(n):
            # 해당돌을 건널 수 없음
            if mid > stones[i]:
                cnt += 1
            else:
                cnt = 0
            
            if cnt >= k:
                can_go = False
                break
            
        if can_go:
            answer = max(mid, answer)
            start = mid + 1
        else:
            end = mid - 1
    
    return answer