[LeetCode]Jump Game

https://leetcode.com/problems/jump-game/

Jump Game - LeetCode

 

문제 분석

nums 배열이 주어졌을 때 마지막 index에 도달할 수 있는지를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 가장 멀리 갈 수 있는 위치 저장
        next_jump_max = 0

        for idx in range(len(nums)-1):
            # 가장 멀리 갈 수 있는 위치 저장
            next_jump_max = max(nums[idx] + idx, next_jump_max)
            
            # 만약 0을 만났을 때 점프해도 더 멀리 갈 수 없는 경우라면 끝까지 도달하지 못함.
            # 최대로 점프할 수 있는 거리가 idx보다 작다면 더이상 전진할 수 없음.
            if nums[idx] == 0 and next_jump_max <= idx:
                return False
                
        # 반복이 종료된 후 최대 점프로 끝까지 도달하지 못한다면
        if next_jump_max < len(nums)-1:
            return False

        return True

# [2,3,1,1,4]
#  0,1,2,3,4
# [2,4,4,4,X]
# if 4 < 4: 


# [3,2,1,0,4]
#  0,1,2,3,4
# [3,3,3,]

접근 방법

1. 반복문을 순회합니다.
2. 가장 멀리 갈 수 있는 위치를 저장합니다.
   가장 멀리 갈 수 있는 위치는 현재의 idx 값 + 등장한 숫자 값과 next_jump_max중 큰 값으로 설정합니다.
3. 만약 반복하다가 0을 만난 경우에 next_jump_max 값이 idx 보다 작다면 더이상 전진할 수 없습니다. False 입니다. (더 앞으로 전진이 불가능한 상태)
4. 반복이 종료된 후에 끝까지 도달하지 못했다면 False 입니다.
5. 아니라면 True 입니다.

반복을 순회하면서 가장 멀리 도달할 수 있는 위치를 계속해서 갱신합니다. 그러다 0을 만난 경우라면 앞으로 전진이 가능한지 살펴봅니다.

반복이 모두 종료되면 끝까지 도달했는지 확인할 수 있습니다.