[Programmers] P64062 징검다리 건너기

[Programmers] P64062 징검다리 건너기

Question

Language: Python

해당 문자를 처음부터 순차적으로 징검다리를 건너는 것을 테스트하면 시간 초과가 발생하게 된다.

최대 반복횟수는 O(NM)이 되는데, 이렇게 하면 20만 * 2억으로 시간복잡도 내에 해결이 불가능하다.

따라서, 위와 같이 반복이 무수히 많은 경우 –> 이분탐색을 고려한다.

어차피, 징검다리에서 중요한 부분은 징검다리의 개수가 아닌, 징검다리 안에 적힌 값이다.

최대 징검다리를 건널 수 있는 최대 사람 수는 1~2억사이다. 그래서 이 사이에서 0인 구간이 k를 넘지 않는 최대값을 구해야한다.

이분 탐색

만약 M에 대해서, 징검다리를 통과할 수 있을 때, 최대값은 M+1 ~ MAX 사이에 존재하게 되고, 징검다리를 통과하지 못하는 경우, 1~ M-1과 같이 범위를 축소 시키면서 최대값을 구하도록 한다.

Solution

def check_stones(stones,m,k):
    count=0
    for stone in stones:
        if stone <= m:        
            count+=1
            #구간의 길이가 k가 넘어서는 순간 이미 징검다리를 통과하지 못하는 것이므로 반복을 종료한다.
            if count>=k:
                return True
        else:
            count=0 
            
    return False
    
def solution(stones, k):
    answer = 0
    start,end=1,200000000
    mid=0
    while start<=end:
        mid=(start+end)//2
        #구간의 길이를 K를 넘게 되면 MAX 값을 줄인다.
        if check_stones(stones,mid,k):
            end=mid-1
        else:
            start=mid+1
    answer=start
    return answer