[Leetcode] 55. Jump Game (python)

#1.  문제

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

Jump Game - LeetCode

 

 

 

 

정수로 이루어진 리스트 nums의 각 요소가 현재 인덱스에서 점프할 수 있는 최대 거리를 나타난다고 했을 때
점프를 통해 마지막 인덱스에 도달할 수 있다면 True 아니면 False를 도출하는 문제

(점프 시작은 무조건 첫 인덱스부터 시작)

 

# input
nums = [2,3,1,1,4]

# output
Output: true

# explanation
무조건 첫 인덱스부터 시작
idx = 0 일때 최대 2칸 갈 수 있다. 
idx = 1 일때 최대 3칸 갈 수 있다.
따라서 idx = 0 에서 1칸 점프하여 idx = 1 로 이동 후 3칸 점프하면 마지막 인덱스 4에 도달

 

---

#2.  풀이

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        last_idx = len(nums) - 1
        finish_idx = len(nums) - 1	# 마지막까지 도달 가능한 특정 인덱스 설정

        for idx, num in enumerate(nums):
            if idx + num >= last_idx:
                finish_idx = idx
                break

        required_list = nums[:finish_idx]

        for i in range(len(required_list) - 1, -1, -1):
            if required_list[i] + i >= finish_idx:
                finish_idx = i

        return finish_idx == 0

 

처음에 문제 예시를 몇가지 만들어보면서 정답을 위한 일종의 패턴이 있는지 확인하려고 했다.

이해하기 쉽게 nums의 인덱스와 요소를 해시맵으로 정리하여 살펴보면

distance = {0:2, 3:1, 2:1, 3:1, 4:4} # 마지막 요소는 무시

특정 인덱스와 요소의 합이 도달하고자 하는 마지막 인덱스와 같거나 크면 도달할 수 있다고 판단했다.

문제는 마지막까지 도달 가능한 특정 인덱스 전까지의 점프 과정을 통해 특정 인덱스까지 도달할 수 있는지가 문제의 핵심이다.

 

idx + num을 통해 특정 인덱스를 추출하고 특정 인덱스 전까지의 리스트를 따로 추출하여 인덱스 오른쪽 요소부터
차례대로 탐색한다.

 

여기 역시 특정 인덱스까지 도달하기 위한 동일한 매커니즘이 적용되야 하므로 idx + num이 특정 인덱스보다 크거나 같으면 특정 인덱스를 바꿔가며 결국 처음 인덱스에서 출발할 수 있는지만 알면 된다.

 

처음 문제를 이리저리 만져보며 재귀로 해결할 수 있을 것 같았는데, 그러한 생각이 문제풀이에 많은 도움을 줬다.