[leetcode] 45. Jump Game II Python

[Problem]
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
 
[Explanation]
There is an array. Each value represents the maximum number of skips to index.
For example, value 5, index 4 can reach from 6 to 9.
 
[Solution]
Actually, the related topic is greedy algorithm. But, in my case, I just used for state with some conditions.
I start from end index.
First, I found a maximum number of skip just by adding index to value.
From that number, I searched the minimum value by adding one to the counted previous number of each index.
Then, if a found count is not 0, it is saved to be used the counted previous number.
 

본 문제의 주 알고리즘은 'greedy algorithm' 이다. 그러나 내가 푼 솔루션의 경우는 몇 개의 조건을 두고 for문을 이용하여 풀었다.

 

class Solution:     def jump(self, nums: List[int]) -> int:         len_nums = len(nums)                  if len_nums <= 1: return 0                  arr = []         arr.append([len_nums - 1, 0]) #index, jump count                  for i in range(len_nums-2, -1, -1):             if nums[i] == 0:                  continue                           idx = i + nums[i]             if idx >= len_nums: idx = len_nums - 1                          cnt = 0                          for j in range(len(arr) - 1, -1, -1):                 if arr[j][0] > idx: break                                                         if arr[j][1] + 1 < cnt or cnt == 0:                      cnt = arr[j][1] + 1                           if cnt != 0: arr.append([i, cnt])                          return arr[-1][1]

Rumtime이나 memory가 하위 수준이다. greedy 알고리즘을 사용하지 않아서 그런것 같다.

greedy 알고리즘을 공부한 뒤 다시 풀어봐야 할 것 같다.