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

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

프로그래머스

 

 

 

돌의 점수를 계산할게 아니라

건널 수 있는 사람의 인원수를 이진탐색으로 체크하는 문제

def solution(stones, k):
    left = 1
    right = 200000000

    while left <= right:

        mid = (left + right) // 2
        print(left, right, mid)
        count = 0

        for stone in stones:
            if stone <= mid:
                count += 1
            else:
                count = 0

            if count >= k:
                break

        if count >= k:
            right = mid - 1
        else:
            left = mid + 1

    return left

 

 

효율성 해결 못 한 코드

def solution(stones, k):
    answer = 0

    while True:
        jump_flag = True
        target = 0

        while True:

            if stones[target] == 0:
                next_jump_flag = False

                for j in range(1, k):
                    if target + j < len(stones) and stones[target + j] != 0:
                        stones[target + j] -= 1
                        target += j

                        next_jump_flag = True
                        break
                    elif target + j == len(stones):
                        next_jump_flag = True
                        target += j
                        break

                if next_jump_flag is False:
                    jump_flag = False
                    break
            else:
                stones[target] -= 1

            if target >= len(stones) - 1:
                target = -1
                answer += 1

            target += 1

        if jump_flag is False:
            break

    return answer