Chloe Jungah Kim
Chloe Jungah Kim
A blogger who writes about everything.

[Leetcode] 55. Jump Game

https://leetcode.com/problems/jump-game/
[Leetcode] 55. Jump Game

양의 정수로 이루어진 리스트가 주어졌을 때, 최대 각 칸의 값만큼 점프할 수 있다고 가정하면, 마지막 인덱스에 도달할 수 있는지 확인하는 문제

  • e.g., 값이 3이라면 1칸, 2칸, 3칸 다음으로 이동할 수 있다.

Example 1

  • Input : nums = [2, 3, 1, 1, 4]
  • Output : true
  • 인덱스 0에서 1칸 이동 -> 인덱스 1에서 3칸 이동

Example 2

  • Input : nums = [3, 2, 1, 0, 4]
  • Output : false
  • 어떤 경우에도 무조건 인덱스 3에 도달할 수밖에 없고, 인덱스 3의 값이 0이므로 마지막 인덱스에 도달할 수 없다.

Note

단순하게 생각하여, 최대로 이동할 수 있는 길이가 리스트의 전체 길이보다 긴지 확인

1
2
3
4
5
6
7
8
9
10

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        far, i = 0, 0
        while i <= far :
            far = max(far, i + nums[i])
            if far >= length - 1 :
                return True
            i += 1
        return False
«
»