Jump Game

Jump Game

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

문제 요약

주어진 정수 배열 nums에서 각 요소가 현재 위치에서 점프할 수 있는 최대 거리가 주어졌을 때, 마지막 인덱스까지 도달 가능한지 판단하는 문제이다.
return boolean(true: 마지막 인덱스 도달 가능, false: 불가능)

예시

nums = [2, 3, 1, 1, 4]
(각 칸의 값은 현재 위치에서 점프 가능한 최대 칸 수)

idx=0: 현재 칸에서 최대 2칸까지 점프 가능, 도달 가능한 최대 idx = 2
idx=1: 최대 3칸 점프 가능, 도달 가능한 최대 idx = 4 -> true
idx=2: 최대 1칸 점프 가능
idx=3: 최대 1칸 점프 가능
idx=4: 마지막 인덱스

nums = [3, 2, 1, 0, 4]

idx=0: 최대 3칸 점프 가능, 도달 가능한 최대 idx = 3
idx=1: 최대 2칸 점프 가능
idx=2: 최대 1칸 점프 가능
idx=3: 최대 1칸 점프 가능
idx=4: 마지막 인덱스 <- 도달 가능한 최대 idx = 3보다 크므로 false

풀이

• 도달할 수 있는 최대 인덱스를 저장하는 reachable_idx 0으로 초기화
• nums 배열 순회
• 현재 idx까지 도달할 수 없는 경우 = idx > reachable_idx
• 현재 idx에서 도달 가능한 최대 인덱스(reachable_idx) 갱신

수도 코드

def sol(nums):
	reach = 0
    
    for i=0...len(nums):
    	if reach보다 현재 인덱스가 더 크다면:  # 현재 인덱스까지 도달할 수 없으므로 
        	return False
        reach = max(reach, 현재 인덱스 + 점프 가능한 칸수)
    
    return True # 도달가능

Solution(Runtime: 427ms)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, jump in enumerate(nums[:-1]):
            if reach < i:
                break
            reach = max(reach, i + jump)

        return True if reach >= len(nums) - 1 else False

Solution(Runtime: 419ms)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable_idx = 0

        for i, jump in enumerate(nums):
            if reach < i:
                return False
            reachable_idx = max(reachable_idx, i + jump)

        return True

배열의 각 요소들은 현재 위치에서 얼마나 최대로 멀리 점프할 수 있는지를 나타낸다. 그래서 최대한 멀리 점프하는 것이 중요하다. (최대값 안에 있는 위치는 당연히 이동 가능)
따라서 이전의 점프로부터 현재의 위치까지 이동이 가능한지 확인하고 가능하다면 최대 도달 idx를 갱신하도록 구현하였다. 그리디 유형이라서 현재의 가장 최선의 선택을 하도록 하였다.