징검다리 건너기

프로그래머스 Lv.3 이진탐색으로 풀이한 문제인 징검다리 건너기 문제입니다.

 

해당 문제의 링크입니다.

 

코딩테스트 연습 - 징검다리 건너기

각 징검다리는 한명이 건너게 되면 건널 수 있는 사람의 수가 줄어들게 되며, 0이 되면 더 이상 해당 징검다리를 건널 수 없습니다. 사람들은 k개의 징검다리를 건너뛸 수 있으므로 k개 이상이 연속으로 0이 되면, 건널 수 없게 됩니다. 징검다리의 배열의 길이는 200,000까지 되며, 200,000,000까지의 값을 가질 수 있으므로 이진탐색으로 풀이해야 함을 유추할 수 있습니다. 

 

check 함수를 선언한 후, 이를 이용해 이진 탐색 코드를 작성하였다.

def solution(s, k):
    def check(n):
        temp = 0
        for idx in range(len(s)):
            if s[idx] > n:
                temp = 0
            else:
                temp += 1
            if temp >= k:
                return False
        return True
    left = 0
    right = 200000000
    while left < right:
        mid = (left+right)//2
        if check(mid):
            left = mid+1
        else:
            right = mid
    return left