LeetCode 55. Jump Game 풀이, 해설, 파이썬
접근
- 현재 pointer 와 닿을 수 있는 최대 거리인 reach 두 변수를 이용한다.
- 닿는 index 중 가장 멀리까지 갈 수 있는 reach 로 계속해서 업데이트 한다.
- reach 만 max 를 이용해 업데이트하고 pointer 는 linear 로 움직인다 O(n).
사고
먼저 최대거리로 포인터를 옮기고 진행이 불가능하면 하나씩 뒤로 무르는 backtracking 이 떠올랐다. 하지만 visit 을 체크하는 과정에서 비효율적이라는 생각이 들어 기각했다.
class Solution:
def canJump(self, nums: list[int]) -> bool:
pointer = 0
reach = nums[pointer]
if reach + 1 >= len(nums):
return True
while pointer < reach:
pointer += 1
reach = max(reach, pointer + nums[pointer])
if reach + 1 >= len(nums):
return True
return False
