leetcode 45. Jump Game II 풀이

문제 : int로 이루어진 list의 첫번째 index에서 시작해서 원소만큼 이동할 수 있을 때. 마지막 원소에 도달하는 최소 횟수를 구하라. (반드시 도달할 수 있는 입력만 주어진다)

Follow up :

 

아이디어 : Jump Game 1 에서 푼 것과 같이 탐색을 진행하며 count 를 증가시킨다. 마지막 원소에 도달하면 count를 return한다.

 

코드 :

 

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        def find(s, e, t):
            if len(nums) <= e:
                return t
            m = -1
            for i in range(s, e):
                m = max(m, i + nums[i])
            s = e
            e = m + 1
            print(s, e, t, m)
            return find(s, e, t+1)
        s = 0
        e = s + nums[s] + 1
        if len(nums) < e:
            e = len(nums)
        ans = find(s, e, 1)
        return ans
        

 

학습 포인트 : Jump Game 1 에서의 풀이는 다소 시간과 메모리를 많이 소모했지만 이 문제에서는 최소 점프 횟수를 구해야하므로 적절한 풀이인거 같다.

 

출처 : leetcode.com/problems/jump-game-ii/