[알고리즘] 프로그래머스 징검다리 건너기 / python

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

프로그래머스

 

✔ 풀이

디딤돌의 크기가 3억으로 매우 크고, 건널 니니즈 친구들의 수도 무제한 이므로 탐색시간이 짧은 이진 탐색을 사용한다.

이진 탐색을 할 대상은 니니즈 친구들의 수 이다. MIN ~ MAX의 범위를 줄여가면서 탐색한다.

check함수에서 디딤돌 - 건넌 니니즈수 가 0보다 작을 때 ck값을 1증가시키고, 0보다 크다면 연속이 아니므로 ck에 다시 0을 넣는다.

크기가 0인 디딤돌이 연속으로 k개 나타날 때 👉 MAX에 mid를 넣어 MIN~mid를 다시 탐색한다.

니니즈 친구들의 수가 mid보다 작을 가능성이 있기 때문이다.

크기가 0인 디딤돌이 연속으로 k개 나타나지 않을 때 👉 MIN에 mid를 넣어 mid~MAX를 다시 탐색한다.

니니즈 친구들의 수가 mid보다 클 가능성이 있기 때문이다.

MIN과 MAX의 차이가 1일때 까지(사이에 정수가 없을때 까지) 반복한다.

반복문이 끝난 후의 MAX값이 니니즈 친구들 수의 최댓값이다.

def check(mid, stones, k):
    ck = 0
    for i in stones:
        if i - mid <= 0:
            ck += 1
        else:
            ck = 0
        if ck >= k:
            return True
    return False

def solution(stones, k):
    answer = 0
    MIN, MAX = 1, 200000000
    while MIN < MAX-1:
        mid = (MIN + MAX) // 2
        if check(mid, stones, k):
            MAX = mid
        else:
            MIN = mid
    return MAX