LeetCode 45. Jump Game II 풀이, 해설, 파이썬
접근
- 현재 pointer 와 닿을 수 있는 최대 거리인 reach, 점프 횟수 카운트, 새로운 reach 후보 변수인 temp 네 가지 변수를 이용한다.
- 닿는 index 중 가장 멀리까지 갈 수 있는 index 를 temp 후보와 비교해 업데이트 한다.
- 이제 점프할 차례 때 가장 큰 temp 값을 보장해주는 곳으로 점프하고
- 이전 pointer에 이어서 후보군을 탐색한다. 지금까지 본 곳 중에서는 지금 자리가 가장 멀리까지 갈 수 있다는 사실을 알기 때문이다.
- 따라서 pointer 가 linear 로 진행하는 것이 곧 시간복잡도 O(n) 이 되며 최적해이다.
사고
앞선 Jump Game 과 다른 점은 reach 를 계속 업데이트 하지 않고 후보군을 끝까지 탐색 후 jump++ 와 reach 변수 재지정이 이루어지는 것이다. 그렇게 뜨문 뜨문 갱신되는 reach 내에서 loop를 반복적으로 돌아준다.
class Solution:
def jump(self, nums: list[int]) -> int:
pointer = 0
reach = nums[pointer]
jump = 0
if len(nums) == 1:
return 0
while True:
if reach + 1 >= len(nums):
return jump + 1
temp = reach
while pointer < reach:
pointer += 1
if pointer + nums[pointer] > temp:
temp = pointer + nums[pointer]
reach = temp
jump += 1
