읽기 전
- 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
- 개인적으로 배운 점을 정리한 글입니다.
문제 링크
문제 풀이
dp로 풀어야 한다는 생각은 들었으나 생각보다 풀이가 너무 간단하면서도 명확해서 당황했다.
0좌표에서 시작하여 현재 좌표 + 현재 값이 점프할 수 있는 최대 위치이며 마지막 위치까지 점프할 수 있다면 true를 반환, 그렇지 않으면 false를 반환해야 한다.
- 초기값은 0좌표 값을 기준으로 시작
- 다음 좌표들에 대해 탐색한 좌표가 탐색 가능한 최대 위치보다 크다면 범위가 초과되어 마지막 위치까지 도달할 수 없음을 의미하므로 false 리턴
- 범위 내에 있으나 현재 위치 + 현재 값이 이동할 수 있는 최대 위치보다 크다면 갱신
- 만약 현재까지 기록된 최대 이동 위치가 주어진 배열길이-1과 같거나 더 크다면 true 반환
python 코드
class Solution:
def canJump(self, nums: List[int]) -> bool:
limit = nums[0]
for i, num in enumerate(nums):
if i > limit:
return False
limit = max(limit, i + num)
if limit >= len(nums) - 1:
return True
return True
'Algorithms > LeetCode' 카테고리의 다른 글
LeetCode #97 Interleaving String (0) | 2021.12.12 |
---|---|
LeetCode #1143 Longest Common Subsequence (0) | 2021.12.12 |
LeetCode #1981 Minimize the Difference Between Target and Chosen Elements (0) | 2021.08.24 |
LeetCode #1976 Number of Ways to Arrive at Destination (0) | 2021.08.24 |
LeetCode #1339 Maximum Product of Splitted Binary Tree (0) | 2021.08.24 |