[프로그래머스] 징검다리 건너기 [Level 3] (python 파이썬)

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

프로그래머스

 

 

 

 

 

 

 

 

 

 

 

 

def solution(stones, k):
    stone_min = min(stones)
    stone_max = max(stones)
    
    if stone_min == stone_max:
        return stone_min
   
    while 1:
        n = 0    
        now = (stone_min + stone_max)//2 
        c = 0
        for stone in stones:
            if stone - now < 0:
                n = n+1
                if n == k:
                    stone_max = now
                    c =1
                    continue
            else:
                n = 0
            
        if c == 0:
            stone_min = now
            if (stone_min+stone_max)//2  == now:
                return now

 

 

 

이 문제는 이분탐색을 통해 해결할 수 있다. 

 

 

stones 배열의 크기는 200,000 이하 이며, 각 원소의 값은 200,000,000 이하이므로, 문제를 처음 봤을 때 가장 처음 먼저 드는 아이디어는 시간 초과 오류가 났다.

 

 

 

 

 

stones를 돌면서 1개씩 빼가며, 한 명씩 건너는 것을 구현하고, 0보다 작은 연속된 구간이 k인 경우 건넌 사람을 리턴하는 방법은 입력값이 매우 큰 경우 시간 오류가 날 것이다. 

 

 

 

 

 

 

 

따라서 stones를 모두 도는 연산을 최소화 할 필요가 있다.

 

 

 

위의 경우에는 1개씩 늘면서 개산하므로 적어도 stones의 최소값 만큼을 stones를 돌 것이다. 

 

 

 

건너는 사람의 수의 범위는 최소값 부터 최대값까지 이다.

 

 

 

 

 

건너는 사람의 수 = (최소값 + 최대값)//2 

최소값 <= 건너는 사람의 수 <= 최대값

 

 

 

 

 

건너는 사람의 수가 정답보다 큰 경우에는 연속된 0보다 작은 수가 k번 이상일 것이다.

 

 

 

 

 

이 경우에는 최대값을 줄여서 건너는 사람의 수를 줄여야 한다.

최대값 = 건너는 사람의 수로 변경 (적어도 건너는 사람의 수보다는 답이 작을 것이므로)

 

 

 

 

 

 

반면에 건너는 사람이 모두 잘 건너고 나면, 이 경우는 건넌 사람의 수가 정답보다 작을 가능성이 있다.

 

 

 

 

 

이 경우에는 최솟값을 늘려서 건너는 사람의 수를 늘려야 한다. 

 최소값 = 건너는 사람의 수로 변경 ( 적어도 건너는 사람의 수보다는 답이 클 것이므로 )

 

 

 

 

 

 

위의 과정을 반복하면서 건너는 사람의 수를 반복할 때, 이전의 수와 현재의 수가 동일 한 경우가 올 것이다.

그 때의 수를 리턴한다. 

 

 

 

 

77을 찾는 이분탐색, 이를 건너는 사람을 찾는 이분탐색으로 생각해보자.