[프로그래머스] 징검다리 건너기 (LV. 3)

문제

[프로그래머스] 징검다리 건너기 (LV. 3)

요약

• n번 밟을 수 있는 디딤돌들이 늘어선 징검다리가 있다.
• 니니즈 친구들은 k개 이하의 거리를 뛸 수 있다.
• 밟을 수 있는 디딤돌 중, 항상 가장 가까운 디딤돌로 뛰어야 한다.
• 몇 명의 친구들이 건널 수 있는지 구하라.

분류

• 이진탐색

풀이

1. 내 풀이

• 건널 수 있는 친구 수, 즉 result를 기준으로 생각하자.
• result의 범위는 min(stones) ~ max(stones) 이다.
• 적절한 result의 값을 이진탐색한다. result보다 작은 stone의 값이 k개 이상 있으면 right 을 갱신, k개 이하 있으면 left 를 갱신하자.

def solution(stones, k):
    left, right = min(stones), max(stones)
    answer = 0

    while left <= right:
        mid = (left + right) // 2 #예비 result

        skip = 0
        for i in range(len(stones)):
            if stones[i] < mid:
                skip += 1
                if skip >= k:
                    right = mid - 1
                    break
            else:
                skip = 0
        if right != mid - 1:
            left = mid + 1
            answer = max(answer, mid)
    return answer