프로그래머스-징검다리 건너기

문제

징검다리 건너기 (2019 카카오겨울인턴)

풀이

문제조건 해석

디딤돌은 한번 밞을 때마다 1씩 줄어들고, 0이 된 디딤돌은 밟을 수 없다. 디딤돌을 밟지 않고 건너뛸 수 있는 거리는 k이다.

최대 몇 명까지 징검다리를 건널 수 있는지를 물어보는 문제.

알고리즘

제한사항 중 stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다. 이 있다. 때문에 200,000,000번 징검다리 건너는 반복문으로 구현하면 시간초과 발생한다.

따라서, 징검다리를 건널 수 있는 사람의 수를 이진 탐색하면서 건널 수 있으면 사람의 수를 늘려주고, 건널 수 없다면 사람의 수를 줄여준다.

코드

def isAcrossAvailable(stones, acrossCnt, k):
    nextStones = list(map(lambda x: x-acrossCnt, stones))
    acc = 0
    for s in nextStones:
        if s <= 0:
            acc += 1
            if acc >= k:
                return False
        else:
            acc = 0
    return True
        
def solution(stones, k):
    n = len(stones)
    answer = 0
    # 건너는 횟수
    left, right = 0, 200000000
    while left <= right:
        mid = (left+right) // 2
        if isAcrossAvailable(stones, mid, k):
            left = mid+1
        else:
            right = mid-1
    return left

배운점

• 특정 값 뿐만 아니라 최댓값 찾는 경우에도 이진탐색 적용할 수 있다.