[Java] 55. Jump Game

문제 파악

 

정수 배열 nums 가 주어지고, 첫번째 인덱스에서 시작한다.

 

인덱스에 주어진 값은 최대로 점프할 수 있는 값이다.

 

마지막 인덱스에 도달할 수 있으면 true 를 없으면 false를 반환해야한다.

 

---

풀이

 

1️⃣

 

내가 떠올린 아이디어는 다음과 같다.

 

1. 현재 위치에서 가장 멀리 뛸 수 있는 인덱스를 확인한다.
   1. 만약 가장 멀리 뛸 수 있는 위치가 배열의 마지막 인덱스 ( nums.length - 1 ) 이상이라면 true 를 반환한다.
2. 현재 위치에서 가장 멀리 뛸 수 있는 인덱스 까지 순회하면서, 다음으로 가장 멀리 갈 수 있는 인덱스를 찾고 이동한다.
   1. [2, 3, 1, 1, 4] 를 예시로 들자면, 현재 위치 0인 2에서 갈 수 있는 인덱스는 1과 2이고 
      인덱스 1은 (1 + 3) = 4번 인덱스 까지 갈 수 있고
      인덱스 2는 (2 + 1) = 3번 인덱스 까지 갈 수 있으므로 
      1번 인덱스로 이동한다.
   2. 만약, 가장 멀리 갈 수 있는 인덱스가 없다면 false를 반환한다.
      [3, 2, 1, 0, 4] 를 예시로 들면, 현재 위치 0인 3에서 갈 수 있는 인덱스는 1, 2, 3 인데
      1, 2, 3 인덱스 모두 3번 인덱스 위치까지 밖에 도달할 수 없으므로 마지막 인덱스에 도달할 수 없다.

 

위 아이디어를 바탕으로 구현해보았다.

 

class Solution {
    public boolean canJump(int[] nums) {
        int start = 0;
        while (true) {
            int maxJump = start + nums[start];

            if (maxJump >= nums.length - 1) {
                return true;
            }

            int maxIdx = start;

            for (int i = start + 1; i <= maxJump; i++) {
            	// 기존보다 더 멀리 갈 수 있는 경우에만 갱신
                if (nums[i] + i > nums[maxIdx] + maxIdx) {
                    maxIdx = i;
                }
            }

            if (start == maxIdx) {
                return false;
            }

            start = maxIdx;
        }
    }
}

 

결과

 

 

2️⃣ 

로직이 조금 복잡한 것 같아서 정돈해서 다시 풀어봤다.

 

핵심 아이디어는 비슷하다.

 

nums 배열을 순회하며 가장 멀리 도달할 수 있는 인덱스를 계속 업데이트하는데, 

 

순회하는 위치가 가장 멀리 도달할 수 있는 인덱스를 넘어가면, 도달할 수 없다는 의미이므로 false를 반환한다.

 

class Solution {
    public boolean canJump(int[] nums) {
        int limit = 0;
        for (int i = 0; i < nums.length; i++) {

            if (i > limit) {
                return false;
            }

            int jump = nums[i] + i;

            if (jump > limit) {
                limit = jump;
            }

        }
        return true;
    }
}

 

결과

시간이 단축되었다.

 

---

📖 회고

생각한 아이디어를 바탕으로 구현한 코드가 통과해서 기분이 좋았다.

 

구현해보고, 코드를 간단하게 리팩토링 해보는 과정은 귀찮고 어려웠지만 나름 재미도 있었다.(다만 시간이 녹았을 뿐..)