[Programmers_Python] 징검다리 건너기

문제

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

 

사용 알고리즘

이분탐색

 

풀이

고려사항

1. 기준이 되는 수보다 같거나 작은 수의 연속 갯수

2. 기준을 이진탐색으로 탐색

 

후기

1. 이 문제의 keypoint는 시간관리이다.

 

2. 처음 슬라이싱을 활용하여 for문으로 문제를 접근하였다.

엄청 단순하고 빨리 풀었지만, 효율성 테스트에서 모두 시간초과가 발생하였다.

주어진 조건의 범위를 보고 이진탐색도 생각하였지만,

이진탐색보다 슬라이싱을 먼저 선택한 이유는

이진탐색은 매번 배열을 확인하여 시간 관리 측면에서 좋지 않을 것이라고 생각했다.

이는 for문에서의 시간 복잡도만 생각하고 슬라이싱하여 max를 구하는 시간을 고려하지 않아서이다.

max를 하는 경우 O(k) 의 시간이 걸리기 때문에 이 방식의 시간복잡도는 O(n) 가 아닌 O(n * k) 였다.

 

3. 하지만, 이진탐색의 경우 O(log(max_stone_value)) 로 주어진 조건 중 최악의 경우(200,000,000)라도 약 28번으로 작다.

따라서 stones 배열을 순회하더라도 시간 복잡도는 O(n * log(max_stone_value)) 으로

k가 클 경우 슬라이싱을 활용한 방식의 시간복잡도 O(n * k) 보다 작다.

k는 배열의 길이까지 범위로 가지기 때문에 최악의 경우 200,000으로 비효율적이다.

 

코드

이분탐색

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

 

시간초과 코드

def solution(stones, k):
    min_val = 1e9
    for i in range(len(stones) - k + 1):
        min_val = min(min_val, max(stones[i:i+k]))
    return min_val

결과