プログラマー-橋を渡る(2019ココア開発者冬季実習)

プログラマー-橋を渡る(2019ココア開発者冬季実習)

https://programmers.co.kr/learn/courses/30/lessons/64062
こちらの探索で近づいてきましたが、正確性しか通らず・・理由は、通過可能な人を特定し、その人がすべて通過できるかどうかをチェックするため、次のコードを使用しているからです.

## 해당인원 모두 건널수 있는지 체크
def check(stones,k):
    now_idx = 0
    while 1:
        flag = 0
        if now_idx >= len(stones):
            break
        if stones[now_idx] == 0:
            for i in range(k):
                flag = 0
                tmp_idx = now_idx+i
                if tmp_idx >= len(stones):
                    return True
                elif stones[tmp_idx] != 0:
                    #stones[tmp_idx]-=1
                    now_idx = tmp_idx
                    break
                flag = 1
        if flag == 1:
            return False
        elif stones[now_idx] >0:
            stones[now_idx]-=1
            now_idx+=1
        
    return True

このチェックしたコードは効率的ではありません.どうしても方法が思いつかず、解説を見るとチェックの論理が斬新だと思います.各位置の石からmid(越えられる人)を減算し、何個の0が生成されたかを確認し、生成された0がk以上であれば越えられない.合格できない人であれば、最大値を更新し、できれば最小値を更新し、答えに最大値を加えることができます.

コード#コード#

def solution(stones, k):
    answer = 0
    left = 1
    right = 200000000 
    while left <= right:
        #건널 수 있는 사람
        mid = (left + right) //2
        zero_block_cnt = 0
        for stone in stones:
            if stone - mid <=0:
                zero_block_cnt +=1
            else:
                zero_block_cnt = 0
            if zero_block_cnt >= k:
                break
        if zero_block_cnt >= k:
            right = mid -1
            continue
        left = mid +1
        answer = left
        
    return answer