20 lines
1.1 KiB
Python
20 lines
1.1 KiB
Python
# Jump Game
|
|
|
|
class Solution:
|
|
def canJump(self, nums: list[int]) -> bool:
|
|
recent_true_idx = len(nums)-1
|
|
for i in range(len(nums)-2, -1, -1):
|
|
if i + nums[i] >= recent_true_idx:
|
|
recent_true_idx = i
|
|
|
|
return True if recent_true_idx == 0 else False
|
|
|
|
"""
|
|
걸린 시간: 33분
|
|
|
|
복잡도: nums 리스트 전체를 순회하기 때문에 시간복잡도는 O(n)이고, idx 기록 변수 외에는 따로 초기화하는 건 없기 때문에 공간복잡도는 O(1)이다.
|
|
|
|
해설: 앞에서부터 한번 가보고 못 가면 돌아와서 다음 경로로 가는 식으로 백트래킹으로 풀어야하나 고민했는데, 그럴 필요 없다.
|
|
어차피 nums의 i번째 인덱스에서 i+nums[i] 범위 안쪽까지는 다 갈 수 있기 때문에 그 범위 안에 끝까지 갈 수 있는 것이 보장된 인덱스가 포함되어 있으면 된다.
|
|
따라서 그 끝까지 갈 수 있는 것이 보장된 인덱스를 끝에서부터 가져올 수 있고, 가장 앞쪽 인덱스만 기억하면 그것이 최선의 보장된 인덱스이다.
|
|
""" |