그리디 알고리즘 추가문제

Question 1: Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

입력: nums = [2,3,1,1,4]

출력: true

---

내 풀이

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        if len(nums) == 1:
            return True
        
        if not nums[0]:
            return False 
        
        can_reach = False 
        
        len_num = len(nums)
        for i in range(len_num-2, -1 ,-1):
            if nums[i] >= len_num-i-1:
                print(nums[:i+1])
                can_reach = self.canJump(nums[:i+1])
                break
            
      
        return can_reach

결과

Runtime: 9014 ms, faster than 5.01% of Python3 online submissions for Jump Game. Memory Usage: 415.8 MB, less than 5.06% of Python3 online submissions for Jump Game.

풀이 1

class Solution:
    def canJump(self, nums):
        m = 0
        for i, n in enumerate(nums):
            if i > m:
                return False
            m = max(m, i+n)
        return True
       

중요 내용

1. i+n은 현재 위치에서 n만큼 앞으로 이동한 위치이다.
2. 만약 최대로 갈 수 있는 위치(m)보다 현재 서 있는 위치(i)가 더 크면 그 위치까지 도달할 수 없다는 의미이므로 마지막 인덱스까지 도달하지 못한다.

---