[Medium] 점프 게임 - 55. Jump Game

정수 배열 nums가 주어집니다. 초기에는 배열의 첫 번째 인덱스에 위치하고 있으며, 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다. 마지막 인덱스에 도달할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

예시 1:

• 입력: nums = [2,3,1,1,4]
• 출력: true
• 설명: 0번 인덱스에서 1번 인덱스로 1칸 점프하고, 이후 3칸을 점프하여 마지막 인덱스에 도달할 수 있습니다.

예시 2:

• 입력: nums = [3,2,1,0,4]
• 출력: false
• 설명: 어떤 경우에도 3번 인덱스에 도달하게 되며, 이 위치의 최대 점프 길이가 0이므로 마지막 인덱스에 도달할 수 없습니다.

제한 사항:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

풀이

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i = -1
        last_index = len(nums) - 1
        max_jump = 0

        while i < max_jump:
            i += 1
            if i + nums[i] > max_jump:
                max_jump = i + nums[i]
            if max_jump >= last_index:
                return True

        return False

 

max_jump는 현재 위치의 인덱스에서 최대한 도달할 수 있는 위치를 나타냅니다. 만약 max_jump의 값이 last_index보다 크거나 같다면 마지막 인덱스에 도달이 가능한 것이므로 True를 리턴합니다. 그렇지 않다면 다음 인덱스로 넘어가서 계산을 합니다. 이 반복문은 현재 위치를 나타내는 i가 max_jump 에 도달할 때까지 실행합니다. max_jump에 도달했는데도 last_index에 도달하지 못한다면 False를 리턴합니다.