LeetCode: 55번 (Jump Game) [JAVA]

문제 링크

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

Jump Game - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 배열 nums와 동일한 길이의 boolean 배열 생성, 배열의 끝 부분은 true로 초기화
2. 배열의 끝 -1 위치에서 반복문을 통해 (해당 위치 + 1) ~ (해당 위치 + 주어진 점프 횟수) 사이를 탐색하며 그 사이 boolean 배열에 true가 확인되면 본인의 위치 값도 true로 변경
3. 2번의 과정을 배열의 시작까지 반복
4. 해당 boolean 배열의 위치 0의 값을 반환

 문제에서 점프를 통해 처음부터 끝까지 도달 가능함을 물어보는 것은 완전 탐색을 통해 진행을 하면 된다. 주어진 nums 배열과 동일한 길이의 boolean 배열을 초기화 후, 목표 위치인 배열의 마지막 부분은 true로 초기화한다. 이후 (배열의 끝 - 1) 위치에서부터 반복문을 통해 탐색을 진행하는데, (해당 위치 + 1) ~ (해당 위치 + 주어진 점프 횟수) 사이를 탐색하며 그 사이 boolean 배열에 true가 확인되면 본인의 위치 값도 true로 변경한다.

 그렇게 앞선 반복문을 배열의 끝에서부터 앞으로 진행을 하며, 이후 반복문이 끝나면 해당 boolean 배열의 첫 번째 요소 결과 값을 반환하면 된다.

 

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] possible = new boolean[nums.length];//가능성 체크 배열
        possible[nums.length - 1] = true;//마지막은 true

        for (int i = nums.length - 2; i >= 0; i--) {//끝에서부터 앞으로
            int stepCount = nums[i];

            for (int j = i + 1; j <= i + stepCount && j < nums.length; j++) {//주어진 횟수만큼
                if (possible[j]) {//앞에 true가 있다면 현재도 true로 변경
                    possible[i] = true;
                    break;
                }
            }
        }

        return possible[0];//시작부분 반환
    }
}

결과