리트코드 - 45. Jump Game II

리트코드 - 45. Jump Game II

출처 - https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 길이 n의 정수 배열 nums가 있습니다 (인덱스는 0부터 시작). 초기 위치는 nums[0]입니다.

각 원소 nums[i]는 인덱스 i에서 가능한 전진 점프의 최대 길이를 나타냅니다.

다시 말해, 만약 nums[i]에 있다면, 0 <= j <= nums[i]이고 i + j < n을 만족하는 모든 nums[i + j]로 점프할 수 있습니다.

nums[n - 1]에 도달하기 위한 최소 점프 횟수를 반환합니다. 테스트 케이스는 nums[n - 1]에 도달할 수 있도록 생성되었습니다.

 

 

의사코드

nowMaxReach  = 0 nextReach  = 0 count = 0 반복문 시작 (i=0 부터 배열의 마지막 전까지)     nowMaxReach = Math.max(nowMaxReach, i + nums[i])     if (i == nextReach)         ++count         nextReach = nowMaxReach; 반복문 종료 count 리턴

 

풀이코드

class Solution {
    public int jump(int[] nums) {
        int nowMaxReach = 0;
        int nextReach = 0;
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            nowMaxReach = Math.max(nowMaxReach, i + nums[i]);

            if (i == nextReach) {
                ++count;
                nextReach = nowMaxReach;
            }
        }
        return count;
    }
}

코드설명

그리디 알고리즘을 활용한 풀이이다. 굳이 따지자면 BFS에 가깝다.

 

이전 JumpGame문제에서는 단순히 끝에 도달할 수 있는가 아닌가가 중요해서 뒤에서 부터 역으로 판단했었다.

하지만 이번에는 최소의 움직임으로 도달할 수 있는지 확인해야 하기 때문에 역방향으로 계산하기가 다소 까다롭다.

 

크게 두 부분으로 나누어 생각해본다.

 

1) 현재 갈 수 있는 위치를 저장한다.

2) 현재 갈 수 있는 위치 끝에 도달할 수 있으면 count를 +1 한다.

 

문제의 조건에서 항상 도달한다는 가정이 있었으므로 도달하지 않는 경우는 생각하지 않고,

nowMaxReach는 배열의 현재값에서 최고로 갈 수 있는 거리를 저장한다.

글보다 그림으로 설명하겠다.

처음 배열에 접근할 때도 count를 +1 해야하고, 다음번 갈수있는 거리까지 도달했을때도 count를 +1 하려면 if (i == nextReach) 라는 조건으로 판단하면 된다.

 

배열의 처음에서 갈수있는 거리는 2가 되고,(i = 0, 배열값 = 2 이므로)

i == nextReach 라는 조건에 의해 count +1 해주면 된다.

그리고 nextReach = nowMaxReach로 갱신해준다.

이제 갈 수 있는 최대거리는 2가 되고,

반복문 순회에 의해 다음 3을 먼저 확인하는데, 갈 수 있는 다음거리는 4로 갱신 된다.(i = 1, 배열값 = 3)

끝에 도달했지만 i != nextReach 이므로 더 순회해준다.

이번 배열의 값에서 갈 수 있는 거리는 2라서(i = 2, 배열값 = 0) nowMaxReach가 갱신은 안된다.

i가 nextReach에 도달했으므로 if분기에 의해 count를 +1 해주고, nextReach도 4로 갱신이 된다.

다음 배열을 순회하지만 이미 nextReach가 4를 바라보고 있으므로, count는 더 갱신될 수가 없다.

즉, 탐욕스럽게 전부 확인은 하되, 올바른 값만 가져올 수 있는 것이다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

그리디 알고리즘을 제대로 써본적이 없어서 다른 코드를 보고 개념을 익히는데 집중하기로 했다.

다른 코드를 보고 로직을 이해하고, 백지부터 직접 구현해보는 것도 꽤 도움이 되는 것 같다.

 

처음에는 백트래킹 방식으로 해야하지 않을까 싶었는데, 무조건 도달한다는 조건이 있으므로 오버 엔지니어링이 아닐까 싶다.

그리디와 DP는 계속 풀면서 감을 익히는 수밖에 없을것 같다.

 

정리

그리디 알고리즘을 이용한 최소의 도달방법 찾기