프로그래머스 징검다리 건너기(Python) - 이분탐색

🖥️문제 링크

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

프로그래머스

 

🎀해결 방법

우선 정확도부터 부수기 위해서 뚝딱뚝딱 구현했다

범위를 어떻게 잡아야할지 몰라서, stones중에 가장 큰 값부터 1까지를 검사했다.

 

정확성은 100점, 효율성은 0점!

 

그러면 효율성을 높이기 위해서 범위를 어떻게 잡아야할까

결국 생각해내지 못하고 찾아봤는데, 0과 최대값 사이에서 이분탐색으로 해결할 수 있었다.

 

 

✨단순 구현 - 효율성 테스트 실패

# 시간초과

def solution(stones, k):
    max_num = max(stones)
    for i in range(max_num,0,-1):
        j = 0
        jump = 0
        while j < len(stones):
            if stones[j] - i < 0:
                jump += 1
            else:
                jump = 0
            if jump >= k:
                break
            j += 1
        if j == len(stones):
            return i
    return 0

정확성: 64.1

효율성: 0.0

합계: 64.1 / 100.0

 

✨단순 구현 + 이분탐색 추가 - 효율성 테스트 실패

동일한 방법인데 while문은 통과가 안될까?!

def solution(stones, k):
    answer = 0
    left, right = 0, max(stones)
    while left <= right:
        mid = (left + right) // 2
        j = 0
        jump = 0
        while j < len(stones):
            if stones[j] - mid <= 0:
                jump += 1
            else:
                jump = 0
            if jump >= k:
                break
            j += 1
        if jump < k:
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    return answer

정확성: 64.1

효율성: 7.7

합계: 71.8 / 100.0

 

✨이분탐색 추가 - 통과

def solution(stones, k):
    answer = 0
    left, right = 0, max(stones)
    while left <= right:
        mid = (left + right) // 2
        jump = 0
        for stone in stones:
            if stone - mid <= 0:
                jump += 1
            else:
                jump = 0
            if jump >= k:
                break
        if jump < k:
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    return answer

이분탐색으로 범위를 잡아주니 효율성을 통과할 수 있었다.

적절히 잘 사용하자!!