LeetCode 55(Jump Game, Python)

1. 문제 링크 

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

Jump Game - LeetCode

2. 문제 설명

• 정수 array인 nums가 주어졌을 때, 초기에는 nums의 첫번째 array에 위치해있으며, 각 element의 값은 최대로 점프할 수 있는 값을 의미
• 이 때, 가장 마지막 index로 도달할 수 있으면 True, 아니면 False를 반환
• 예시1) nums=[2,3,1,1,4]의 경우, index 0에서 1, 1에서 3step 이동하면 가장 마지막 index로 도착할 수 있으므로 True 반환 
• 예시2) nums=[3,2,1,0,4]의 경우 무슨 수를 써도 index 3까지만 이동 가능함. (index 3의 최대 점프 가능 길이가 0이기 때문) 따라서 false 반환.

3. 처음 풀이

• 우선 len(nums)가 1이면, 시작 index와 종료 index가 같으므로 True 반환 (이동하지 않고, last index로 갈 수 있으니)
• 나머지 케이스에 대해서 for문을 돌리면서, farthest 값을 업데이트. 여기서 farthest는 가장 멀리 갈 수 있는 거리를 뜻함 
  • 만약 가장 멀리 갈 수 있는 거리 (farthest)가 index i보다 작다면, i까지 올 수 없다는 것을 의미하므로 False반환
  • i+nums[i]가 farthest보다 크면 farthest를 업데이트
  • 최종적으로 farthest >= len(nums)-1를 반환

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        if len(nums) == 1:
            return True        

        farthest = -1

        for i in range(len(nums)-1):
            if farthest < i and i != 0:
                return False

            if i+nums[i] > farthest:
                farthest = i+nums[i]

        return farthest >= len(nums)-1

 

4. 다른 풀이 

• 처음 풀이와 접근은 거의 비슷함
• 아래 풀이의 경우, 가장 멀리갈 수 있는 거리를 업데이트 하지 않고, goal이라는 변수를 두고 가장 마지막 인덱스에서 앞으로 이동하면서, goal==0 (첫번째 인덱스까지 이동) 이면 True, 아니면 False를 반환하는 구조로 코드 작성
  • 이렇게 하면, 굳이 len(num)==1 인 케이스에 대해 예외 조건을 두지 않아도 된다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1
        
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        
        if goal == 0:
            return True
        else:
            return False