LeetCode #55 Jump Game

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #55 Jump Game

문제 풀이

dp로 풀어야 한다는 생각은 들었으나 생각보다 풀이가 너무 간단하면서도 명확해서 당황했다.

0좌표에서 시작하여 현재 좌표 + 현재 값이 점프할 수 있는 최대 위치이며 마지막 위치까지 점프할 수 있다면 true를 반환, 그렇지 않으면 false를 반환해야 한다.

• 초기값은 0좌표 값을 기준으로 시작
• 다음 좌표들에 대해 탐색한 좌표가 탐색 가능한 최대 위치보다 크다면 범위가 초과되어 마지막 위치까지 도달할 수 없음을 의미하므로 false 리턴
• 범위 내에 있으나 현재 위치 + 현재 값이 이동할 수 있는 최대 위치보다 크다면 갱신
• 만약 현재까지 기록된 최대 이동 위치가 주어진 배열길이-1과 같거나 더 크다면 true 반환

python 코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        limit = nums[0]
        for i, num in enumerate(nums):
            if i > limit:
                return False
            limit = max(limit, i + num)
            if limit >= len(nums) - 1:
                return True
        return True