•
문제 링크 : 
LeetCodeJump Game - LeetCode
•
문제 설명 : 각 요소에 현재 인덱스에서 점프 가능한 인덱스의 최대 값을 나타낸다. 마지막 요소까지 이동이 가능한지 구한다.
•
풀이 방법
◦
여러 방법을 사용했지만, 결국 예외 처리를 못하여 솔루션을 확인하였다.
◦
솔루션은 굉장히 간단한 방법이라 허탈했는데, 이런 아이디어를 떠올리는게 신기할뿐이다.
▪
이 솔루션을 작성한 사람은 점프가 아닌, 자동차가 이동하는 것이라고 생각했다.
▪
그리고, 각 요소를 하나의 가스 충전소라고 생각하였으며 해당 가스 충전소에서 충전 시 최대 이동 가능한 거리가 갱신된다고 생각하였다.
◦
즉, 현재 남은 연료 < 주유소의 최대 충전량 일때 무조건 충전(갱신) 한다고 하면 마지막에 도달이 가능한지 확인할 수 있다.
•
시간복잡도 :
•
성공 코드
class Solution:
def canJump(self, nums: List[int]) -> bool:
gas = 0
for n in nums:
# 더 이상 이동이 불가할 때
if gas < 0:
return False
# 현재 이동 가능 거리보다 더 많은 이동이 가능하도록 갱신이 가능할 때
elif n > gas:
gas = n
# 인덱스 이동 시, 이동 가능 거리를 1씩 줄인다.
gas -= 1
return True
Python
복사