Jump Game

LeetCode 55. Jump Game

원문

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

풀이

발상

nums를 순회하며 점프할 수 있는 범위 내의 위치를 방문처리해준다.
이때 방문처리가 되어 있지 않은 지점은 continue

시간 초과

코드: 시간 초과

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        visited = [False for i in range(len(nums))]
        visited[0] = True

        for i in range(len(nums)):
            if not visited[i]: continue
            for j in range(1, nums[i] + 1):
                if i + j < len(nums):
                    visited[i + j] = True
                else: break

        return visited[-1]

앞부터 보았으니 이번에는 뒤부터 보자

1. 가장 마지막 지점을 True로 표시한다.
2. 마지막 직전 지점부터 앞으로 순회하면서 그 지점(i)에서 점프할 수 있는 최대 지점이 마지막 지점 이상이면 그 지점도 True로 표시한다.
3. 그렇지 않은 경우 이동할 수 있는 범위를 순회하며 그 안에 True인 지점이 있으면 i도 True로 바꾸고 안쪽 반복문에서 나온다.
4. 순회가 끝나면 시작 지점의 상태를 반환한다.

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1: return True
        dp = [False for i in range(len(nums))]
        dp[-1] = True
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] + i >= len(nums) - 1: dp[i] = True
            else:
                for j in range(i + 1, i + nums[i] + 1):
                    if dp[j]:
                        dp[i] = True
                        break
        return dp[0]

Java

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }

        boolean[] dp = new boolean[nums.length];
        dp[nums.length - 1] = true;

        for (int i = nums.length - 2; i > -1; i--) {
            if (nums[i] + i >= nums.length - 1) {
                dp[i] = true;
            } else {
                for (int j = i + 1; j < i + nums[i] + 1; j++) {
                    if (dp[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[0];
    }
}

다른 방법

이 영상을 참고했다.

탐욕법

위에서 언급한 영상에서는 골대(도착해야 하는 지점)를 점점 앞으로 당겨오는 것으로 비유했다.

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 1, -1, -1):
            if i + nums[i] >= goal:
                goal = i

        return False goal else True

도착 지점을 goal이라고 했을 때, nums을 뒤에서 앞으로 순회하면서 순회하는 지점이 goal에 도달할 수 있다면 goal 값을 그 지점으로 변경한다.

Java

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length - 1;

        for (int i = nums.length - 1; i > -1; i--) {
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }

        if (goal == 0) {
            return true;
        }
        return false;
    }
}