[코딩/LeetCode150-(9)] 55. Jump Game

 

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: Medium

키워드: Array, DP

 

문제

 

문제 원문: https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150 

 

정수형 배열 nums가 주어졌다고 하자. 당신은 처음에 배열의 첫번째 index에 위치한다. 그리고 배열의 각 원소는 해당 위치에서부터 당신이 최대로 점프할 수 있는 길이를 나타낸다. 이 때, 마지막 index 에 도달할 수 있는 경우 true, 아닌 경우 false를 반환하라.

 

예제 입력

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

문제 풀이

풀이 1. DP (Top-down approach)

문제에서 가능성 여부를 물어보고있고, 이 때 몇 번째 index를 선택하느냐에 따라 마지막 index에의 도달 여부가 달라질 수 있으므로 Dynamic Programming을 사용해서 문제를 풀고자한다. 우선, 별도의 최적화 없이 가장 간단하게 구현할 수 있는 Top-Down approach를 사용하면 다음과 같이 문제를 해결할 수 있다.

 

1) 종료 조건은 마지막 index에 도달하는경우 return True

2) 그 다음 state는 현재 위치 i에서부터 올라갈 수 있는 최대 높이까지의 각각의 위치에서 도달 가능한 여부 탐색

-> 하나라도 도달 가능하면 return True

-> 모두 조회해보고 불가능하면 return False

 

이를 종합해서 구현하면 다음과 같다.

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        @cache
        def dp(i):
            if i >= len(nums)-1:
                return True
            for j in range(i+1, i+nums[i]+1):
                if dp(j):
                    return True
            return False
        
        return dp(0)

🕰 Runtime 5495 ms 

💻 Memory 56.1 MB

 

풀이 2. DP (Bottom-up approach)

재귀 함수를 사용하는 방식 1은 아무래도 overhead로인해 속도가 느리다. 이를 개선하기 위해서 recursion을 array 순회로 대체하는 것이 필요하다. 따라서, 방식 1의 종료조건에서부터 역으로 0 index까지 도달이 가능한지 여부를 확인하도록 코드를 작성해보았다.

 

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

        N = len(nums)
        if N == 1:
            return True

        dp = [False] * N

        # basecase
        dp[-1] = True
        for i in range(len(nums)-1,-1,-1):
            for j in range(i+1, min(i+nums[i]+1, N)):
                if dp[j]:
                    dp[i] = True
                    break
        
        return dp[0]

 

🕰 Runtime 2499 ms

💻 Memory 17.5 MB

 

풀이 3. DP (Bottom-up approach) 변형

 

DP 알고리즘에서 굳이 전체 dp에 대한 순회를 해줄 필요가 없다. 최대 최소 값을 묻는게아니라 그냥 가능성을 물어보는것이기때문에. 그래서 목적지 (top)를 매번 갱신해주고 현재 step에서 목적지에 도달 가능한지 여부를 판단하도록 코드를 수정하였다.

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        N, top = len(nums), len(nums)-1
        for i in range(N-2,-1,-1):
            if (i + nums[i] >= top):
                top =  i
        return True if (top == 0) else False

🕰 Runtime 384 ms

💻 Memory 17.5 MB