<Medium> Jump Game (LeetCode : C#)

https://leetcode.com/problems/jump-game/

📕 문제 설명

최대 점프 길이를 담고 있는 배열이 주어질 때 마지막 위치에 도달할 수 있는지에 대해 반환

• Input
  최대 점프 길이를 담은 배열 (int[])
• Output
  마지막 위치 도달 여부 (bool)

예제

풀이 1.

방문 표시 두고 max jump에 대해 모든 가능한 케이스로 점프해보는 완전 탐색 (O(N^2))

public class Solution {
    public bool CanJump(int[] nums) {
        bool[] visited = new bool[nums.Length];
        visited[0] = true;

        for (int i = 0; i < nums.Length; i++)
        {
            if (visited[i])
            {
                for (int j = 1; j < nums[i] + 1; j++)
                {
                    if (i + j >= nums.Length) break;
                    visited[i + j] = true;
                }
            }
        }

        return visited[nums.Length - 1];
    }
}

결과 1.

풀이 2.

매 점프별로 완전 탐색 안하고 최대 점프 수를 갱신해나가며 푼다면 O(N)으로 들어올 수 있다.

1) 최대 점프수보다 현재 index가 가리키는 최대 점프 수가 더 크다면 최대 점프수 갱신
2) 최대 점프수보다 현재 index가 가리키는 최대 점프 수가 더 작다면 최대 점프수 - 1 (이번 칸 뛰어 넘는다는 의미)
3) 만약 현재 더 이상 최대 점프수 갱신 안되는데 (nums[i] == 0) 최대 점프 수도 더이상 없으면 false, 그 외는 true

public class Solution {
    public bool CanJump(int[] nums) {
        int maxJump = 0;

        for (int i = 0; i < nums.Length - 1; i++)
        {
            if (nums[i] == 0 && maxJump == 0) return false;
            if (nums[i] >= maxJump) maxJump = nums[i];
            maxJump -= 1;
        }

        return true;
        
    }
}

결과 2.