[프로그래머스, 파이썬] 징검다리 건너기 - 레벨 3 | 이진탐색

📌 프로그래머스 Level 3 : 징검다리 건너기

처음에 아무 생각 없이 while문 돌려서 stones 모든 Inde에 -1씩 해주고 k번 이상 뛰어넘게 되면 while문 탈출해서 답을 구하도록 짰는데, 역시나 효율성 테스트에서 통과하지 못했다.

한 번 통과 못하니까 바로 이진 탐색 써야겠다는 생각이 들었다..

📋 내 풀이

def solution(stones, k):
    answer = 0
    """
    k칸을 뛰어넘지 않는 한도에서 최솟값을 이진탐색으로 구하자
    
    left는 1로, right는 max 함수 써서 구하니까 더 빠르게 구해졌다.
    """
    left = 1
    right = max(stones)
    
    while left <= right:
        mid = (right+left) // 2
        cnt = 0
        
        for i in range(len(stones)):
            if stones[i] - mid <= 0:
                cnt += 1
            else:
                cnt = 0
            if cnt >= k:
                break
        
        if cnt >= k:
            right = mid - 1
            answer = mid
        else:
            left = mid + 1
        
    return answer

채점 결과

정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 9.91MB)
테스트 3 〉 통과 (0.02ms, 9.99MB)
테스트 4 〉 통과 (0.02ms, 10MB)
테스트 5 〉 통과 (0.02ms, 10.4MB)
테스트 6 〉 통과 (0.32ms, 10.4MB)
테스트 7 〉 통과 (0.78ms, 9.91MB)
테스트 8 〉 통과 (0.78ms, 10.3MB)
테스트 9 〉 통과 (0.80ms, 10.1MB)
테스트 10 〉 통과 (0.03ms, 10.4MB)
테스트 11 〉 통과 (0.01ms, 10.3MB)
테스트 12 〉 통과 (0.02ms, 10.2MB)
테스트 13 〉 통과 (0.04ms, 10.2MB)
테스트 14 〉 통과 (0.49ms, 10.1MB)
테스트 15 〉 통과 (0.86ms, 10MB)
테스트 16 〉 통과 (0.56ms, 10.4MB)
테스트 17 〉 통과 (1.25ms, 10.2MB)
테스트 18 〉 통과 (0.01ms, 10.4MB)
테스트 19 〉 통과 (0.03ms, 10.2MB)
테스트 20 〉 통과 (0.06ms, 10.2MB)
테스트 21 〉 통과 (0.56ms, 10.2MB)
테스트 22 〉 통과 (0.85ms, 10.3MB)
테스트 23 〉 통과 (0.79ms, 10.4MB)
테스트 24 〉 통과 (0.80ms, 10.2MB)
테스트 25 〉 통과 (0.01ms, 10.2MB)

효율성 테스트
테스트 1 〉 통과 (371.63ms, 18.5MB)
테스트 2 〉 통과 (408.08ms, 18.5MB)
테스트 3 〉 통과 (443.08ms, 18.5MB)
테스트 4 〉 통과 (293.90ms, 18.6MB)
테스트 5 〉 통과 (311.59ms, 18.5MB)
테스트 6 〉 통과 (353.97ms, 18.6MB)
테스트 7 〉 통과 (477.72ms, 18.5MB)
테스트 8 〉 통과 (496.83ms, 18.5MB)
테스트 9 〉 통과 (444.19ms, 18.5MB)
테스트 10 〉 통과 (484.84ms, 18.6MB)
테스트 11 〉 통과 (414.82ms, 18.6MB)
테스트 12 〉 통과 (480.35ms, 18.5MB)
테스트 13 〉 통과 (355.21ms, 18.5MB)
테스트 14 〉 통과 (245.50ms, 18.6MB)
채점 결과
정확성: 64.1
효율성: 35.9
합계: 100.0 / 100.0

이진탐색으로 풀어야겠다고 생각이 들면 그렇게까지 어려운 문제는 아닌 것 같다.

단지.. 처음에 left right 설정 부분이 조금 중요했는데,

left = min(stones)
right = max(stones)

으로 지정했을 때 효율성 테스트 8번에서 시간 초과가 일어났고,

left = 1
right = max(stones)
#혹은 right = 200000000

로 수정했을 때 정상적으로 모두 통과가 됐다.

min() max()함수는 전체를 다 돌면서 최소, 최댓값을 구해야하기 때문에 시간복잡도가 O(N)이다.

그래서 효율성을 요구하는 문제에는 신중하게 사용해야한다!
(사용하지 않을 수 있으면 그러는게 좋음)