[LeetCode] 55. Jump Game

Jump Game - LeetCode

 

int 배열이 주어지면 배열의 첫번째 인덱스부터 점프해서 마지막 인덱스까지 도달할 수 있는지 확인하는 문제입니다.

배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다

predicate 형식으로 반환하면 됩니다.

 

문제 접근

주어진 배열의 요소들을 하나씩 탐색해가면 해당 인덱스의 요소만큼 점프를 해야합니다.

 

저는 재귀함수를 통해 접근해보았습니다.

재귀함수에서 for문을 통해 요소 하나씩 접근하여 차례차례 접근하는것입니다.

 

 수도코드

main () {
	return dfs() > 0
}

dfs () {
	if depth == n:
    	return 1;
    
    for ~ nums[depth]
    	dfs(depth+1);
}

 

코드

    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        final int result = dfs(0, nums, nums.length);
        return result > 0;
    }

    public int dfs(int depth, int[] nums, int to) {
        int ret = 0;
        if (depth > to) {
            return 0;
        }

        if (depth == to-1) {
            return 1;
        }

        for (int i = 1; i <= nums[depth]; i++){
            ret += dfs(depth + i, nums, nums.length);
        }
        return ret;
    }

 

시간복잡도

시간초과가 발생했습니다.

그 이유는 아래와 같습니다.

nums.length : 10의 4승

nums[i] : 10의 5승

 

재귀 호출을 하면 스택에 메모리도 계속 쌓이니 공간복잡도도 올라가고

재귀 호출을 최악의 경우 10의4승 * 10의 5승 까지하기때문에

시간초과가 발생하는 코드입니다.

 

다른사람의 풀이

뒤에서부터 접근하여 현재인덱스가 마지막 인덱스에 올 수 있는지 판단하고

만약 접근할 수 있다면 pos를 해당 인덱스로 바꾸는 것입니다. 

 

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int pos = n - 1;
        for (int i = n-2; i >= 0; i--){
            if (pos <= i + nums[i]){
                pos = i;
            }
        }
        return pos == 0;
    }

 

느낀점

max와 min을 구해서 정답을 도출하는 방법은 정말 다양한 곳에 쓰이는것 같습니다.

 

 

참고

https://www.youtube.com/watch?v=D8wsM1rowUk