[leetcode] 55. Jump Game

문제 설명

링크
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.

접근 1

• 첫 인덱스부터 시작해서, 해당 칸에 도착할 수 있으면 해당 칸에서 갈 수 있는 곳들을 표시하는 방식
• 굉장히 느림

코드 1

    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = True
        for i in range(n- 1):
            if dp[i]:
                for step in range(1, nums[i] + 1):
                    if i + step == n - 1: return True
                    if i + step < n: dp[i + step] = True
        return dp[-1]

접근 2 - O(n)

• [2,3,1,1,4] 일 때, m 의 변화 --> 0 2 4 4 4
• 최대 거리를 구해놓고 해당 인덱스에 도달하지 못했을 경우 False 를 반환하는 것

코드 2

    def canJump(self, nums):
        m = 0
        for i in range(len(nums)):
            if i > m:
                return False
            m = max(m, i + nums[i])
        return True

접근 3 - faster

• 거꾸로 가면서 debit 을 하나씩 늘려준다
• jump 가능한 길이가 debit 보다 크다면 가능한 것이므로 debit 을 0으로 초기화 해준다
• debit ==0 이라면 도달 가능한 것

코드 3

    def canJump(self, nums: List[int]) -> bool:
        debit = 0
        for i in reversed(nums[:-1]):
            debit += 1
            if i - debit >= 0:
                debit = 0
        return debit == 0