[Leetcode] 55. Jump Game_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '55. Jump Game'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Jump Game' 알고리즘 문제

 

STEP 2. 'Jump Game' 코드(code)

 

STEP 3. 'Jump Game' 해설

 

STEP 4. 'Jump Game' solution

 

반응형

 

STEP 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가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며, 배열의 각 요소는 해당 위치에서의 최대로 이동할 수 있는 길이를 나타냅니다. 마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

 

---

STEP 2. 'Jump Game' 코드(code)

 

■ Runtime: 407ms Beats 63.97%
■ Memory: 17.58MB Beats 39.08%

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Take curr variable to keep the current maximum jump...
        curr = nums[0]

        for i in range(1, len(nums)):
            # If the current index 'i' is less than current maximum jump 'curr'...
            # It means there is no way to jump to current index...
            # so we should return false...
            if curr == 0:
                return False
            curr -= 1

            # Update the current maximum jump...
            curr = max(curr, nums[i])

        return True

 

---

STEP 3. 'Jump Game' 해설

 

마지막 인덱스로 이동하기 위해서는 인덱스를 이동하면서 더 이상 이동하지 못하는 0이 되는 경우를 제외하면 됩니다. 이를 위해 직전 인덱스까지 고려하여 최대로 이동 거리 curr과 현재 이동 거리인 nums [i]를 검토해야 합니다.

 

curr는 인덱스를 이동하면서 1씩 감소해야 되기에, curr -= 1을 적용합니다.

 

이때 loop 마지막에 curr과 nums[i] 중 최대 값을 비교하여, 0이 되면 더 이상 이동하지 못하는 상태임을 확인할 수 있습니다. 해당 경우에는 false를 반환하고, 이를 제외한 경우에는 마지막 인덱스까지 도달할 수 있기에 true를 반환합니다.

 

728x90

 

STEP 4. 'Jump Game' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 434ms Beats 30.61%
■ Memory: 17.53MB Beats 39.08%

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable_idx = 0
        for i, num in enumerate(nums):
            if i > reachable_idx:
                return False  # Can't move past the current index
            reachable_idx = max(reachable_idx, i + num)
        return True

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '55. Jump Game'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.