45. Jump Game II

문제 링크 : https://leetcode.com/problems/jump-game-ii/

주어진 배열 nums에서 마지막 인덱스까지 도착할 수 있는 최소 이동 횟수를 구하는 문제이다.

예를 들어 nums = [2,3,1,1,4] 이 주어졌을 떄
일단 맨 처음 2부터 시작하게 된다.

그리고 l포인터, r포인터가 있다고 쳤을 떄

맨 처음 숫자가 2이므로
점프해서 갈 수 있는 범위는 3부터 1까지일 것이다.
이 범위의 시작과 끝을 l,r로 정하고
해당 범위 내애서 다음으로 점프할 범위를 정할 떄 가장 최대로 갈 수 있는 범위를 step으로 하고 가장 최대값을 서치하여 이후 l을 r(끝 포인터)다음 범위로 옮겨주고 r을 step 범위만큼 옮겨준다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        l=0
        r=0
        
        while r < len(nums)-1:
            step = 0
            for i in range(l,r+1):
                step = max(step , i + nums[i])
            l = r+1
            r=step
            ans += 1
        return ans

22.11.27복습