징검다리 건너기

징검다리 건너기
2019 카카오 개발자 겨울 인턴십 
1188명 완료

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

이진탐색 문제
https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search

 

def solution(stones, k):
    def cross(num):
        jump = 0
        for stone in stones:
            if stone > num:
                jump = 0
            else:
                jump += 1
            if jump == k:
                return False
        return True

    answer, left, right = 0, 1, max(stones)
    while left <= right:
        mid = (left + right) // 2
        if cross(mid):
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    return answer

정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.20ms, 9.96MB)
테스트 7 〉	통과 (0.47ms, 9.98MB)
테스트 8 〉	통과 (0.44ms, 10.3MB)
테스트 9 〉	통과 (0.44ms, 10.3MB)
테스트 10 〉	통과 (0.02ms, 10.1MB)
테스트 11 〉	통과 (0.02ms, 10.1MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.03ms, 10MB)
테스트 14 〉	통과 (0.17ms, 10.2MB)
테스트 15 〉	통과 (0.47ms, 10.1MB)
테스트 16 〉	통과 (0.32ms, 10.1MB)
테스트 17 〉	통과 (0.38ms, 10MB)
테스트 18 〉	통과 (0.01ms, 10.1MB)
테스트 19 〉	통과 (0.02ms, 10.1MB)
테스트 20 〉	통과 (0.04ms, 10MB)
테스트 21 〉	통과 (0.38ms, 10MB)
테스트 22 〉	통과 (0.47ms, 10MB)
테스트 23 〉	통과 (0.49ms, 10.1MB)
테스트 24 〉	통과 (0.45ms, 10.1MB)
테스트 25 〉	통과 (0.01ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (224.03ms, 18.6MB)
테스트 2 〉	통과 (246.22ms, 18.5MB)
테스트 3 〉	통과 (223.53ms, 18.6MB)
테스트 4 〉	통과 (132.63ms, 18.6MB)
테스트 5 〉	통과 (155.04ms, 18.5MB)
테스트 6 〉	통과 (177.10ms, 18.5MB)
테스트 7 〉	통과 (302.58ms, 18.5MB)
테스트 8 〉	통과 (308.98ms, 18.5MB)
테스트 9 〉	통과 (246.98ms, 18.6MB)
테스트 10 〉	통과 (302.67ms, 18.5MB)
테스트 11 〉	통과 (233.38ms, 18.6MB)
테스트 12 〉	통과 (269.51ms, 18.5MB)
테스트 13 〉	통과 (162.81ms, 18.6MB)
테스트 14 〉	통과 (127.52ms, 18.6MB)