[Leetcode Top Interview 150] 55. Jump Game

난이도 : medium

문제링크

• int 배열인 nums가 주어짐
• 각각의 요소는 maximum jump length를 뜻함
• 0번째 인덱스부터 시작함
• 맨 마지막 인덱스에 도착할수 있는지 여부를 리턴하세요

 

1. 접근법

• 인덱스 ~ 1 값까지 깊이탐색을 시작한다
• 한건이라도 첫번째 인덱스에 도착할 수 있다면 true 리턴

 

2. 의사코드

public boolean canJump(int[] nums) {
    int start = nums[0];
    for (start ~ 1까지 반복) {
        if (dfs 탐색하여 true를 반환하면) {
            return true;
        }
    }

    // 아니면 retrun false;        
    return false;
}
    
private boolean dfs(int[] nums, int idx) {                
    if (idx가 마지막 인덱스 혹은 그 이상으로 들어올 경우) {
        return true;
    }

    int start = nums[idx], nextIdx;
    for (int i = start; i > 0; i--) {
        nextIdx = idx+i;                        
        if (dfs 탐색하여 true를 반환하면) {
            return true;
        }            
    }

    return false;
}

 

3. 구현 코드

boolean[] canJump;

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

    canJump = new boolean[nums.length];
    Arrays.fill(canJump, true);

    int start = nums[0];
    for (int i = start; i > 0; i--) {
        if (dfs(nums, i)) {
            return true;
        }
    }

    return false;
}

private boolean dfs(int[] nums, int idx) {
    if (idx >= nums.length-1) {
        return true;
    }

    int start = nums[idx], nextIdx;
    for (int i = start; i > 0; i--) {
        nextIdx = idx+i;
        if (nextIdx >= nums.length || !canJump[nextIdx]) {
            continue;
        }

        if (dfs(nums, nextIdx)) {
            return true;
        }

        canJump[nextIdx] = false;
    }

    return false;
}

• dfs탐색을 하면서, 메모이제이션 기법을 적용하였음
• nextIdx에 dfs탐색을 하였으나 찾지 못하였으면
  • 다음번 반복에서 nextIdx로 탐색할 필요가 없으므로 continue

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n^2) - 모든 데이터에 n번 재귀호출이 일어나는 경우
• 공간복잡도 : O(n) - 메모이제이션을 위한 n size의 boolean 배열을 생성함

 

5. 개선점

• 시간복잡도를 O(n)으로
• 공간복잡도를 O(1)로

 

6. 회고

• 개선점을 찾지못해 풀이를 보았다

public boolean solutionCanJump(int[] nums) {
    int lastGoodIndexPosition = nums.length-1;
    for (int i = nums.length-1; i>=0; i--) {
        if (i + nums[i] >= lastGoodIndexPosition) {
            lastGoodIndexPosition = i;
        }
    }

    return lastGoodIndexPosition == 0;
}

(출처 : NickWhite)

• 그리디 알고리즘을 사용하여 풀었다
• 중간에 끝으로 가는 다리가 끊기면, 맨 뒤에 도달할 수 없다
• 뒤에서부터 순회하면서, 현재에서 이전 반복까지의 가장 마지막 인덱스로 점프할 수 있는지 여부를 체크한다
  • 점프할 수 있다면, 마지막 인덱스를 현재 인덱스로 업데이트한다
• lastGoodIndexPosition이 0인지 체크하여 답을 반환한다