[Leetcode]_55. Jump Game

문제

https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

풀이

처음에 접근을 투포인터로 접근해보았다.

 

• 현재의 위치 = i
• 다음의 위치 = 현재 위치 + 현재 위치의 값 = j

위와 같이 설정한 뒤, 다음의 위치가 배열의 마지막 요소의 위치보다 크거나 같으면 True를 반환하고 그렇지 않으면 while 반복문 내부에서 조건을 설정하여 풀어보려고 했다.

 

하지만, 예외적인 상황이 많아서 코드가 복잡해지고 결국 해결하지 못했다. 투 포인터 말고 다른 방법을 시도해야겠다고 생각했다.

 

그래서 풀이를 참고하여 이해해보려고 노력했다.

def canJump(nums):
    curr = nums[0]
    
    for i in range(1, len(nums)):
    	if curr == 0:
        	return False
        curr -= 1
        curr = max(curr,nums[i])
    return True

• 현재 최대 점프값을 유지하기 위해 변수에 저장한다.
• 현재 요소 다음 요소부터 모든 요소를 순회하면서 현재 최대 점프값에서 1을 뺀 값과 현재 인덱스의 요소값 중 큰 값을 curr 변수에 할당한다.
  • 최대 점프값에서 1을 빼주는 이유는 반복문을 순회하면서 한칸 이동하는 것이 점프한 것으로 계산되기 때문이다.
  • 그러므로 둘 중 큰 값을 curr 변수에 할당해주는 것이 현재 최대 점프값을 유지하는 방법이다.
• 1을 빼준 값과 현재 요소의 점프값이 curr 변수에 저장되다보면서 0인 요소가 등장하고 현재 최대 점프 값에서 1을 뺀 값이 0인 경우 curr 점프 최대값이 0이 된다.
  • 마지막 요소 까지 순회하기 전에 curr 변수가 0이 되었다면 마지막 요소에 도달할 수 없다는 의미이므로 False를 반환한다.
  • 마지막 요소 까지 모두 순회에 성공하면 True를 반환