징검다리 건너기

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

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

def solution(stones, k):
    def cross(num): # num의 인원이 징검다리를 건널 수 있는지 판단하는 함수
        fail = 0
        for i in stones:
            if i < num:
                fail += 1
                if fail == k: # k(점프 가능 거리) 보다 fail(건널 수 없는 다리 길이)이 길어지면,
                    return False
            else:
                fail = 0
        return True

    max_case = max(stones) # 돌의 숫자 중 가장 큰것을 maximum 경우로 지정
    min_case = 1 # 문제 제한 사항에 의해 한 명은 건널 수 있음

    while min_case < max_case - 1: # 이분 탐색
        mid = (min_case + max_case) // 2
        if cross(mid):
            min_case = mid
        else:
            max_case = mid

    if cross(max_case): 
        return max_case
    else:
        return min_case

→ O(nlogn) 아니면 효율성 테스트를 단 하나도 통과 못한다...