[Leetcode] 45. Jump Game II - JS

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

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 nums, 배열 길이 n, 초기에 nums[0]에 위치함
- 각 요소 nums[i]는 i위치에서의 최대 점프 길이
- 마지막 요소에 도달 가능한 배열만 주어진다.
- 마지막 위치(nums[n - 1])에 도달하는 최소한의 점프 수를 반환하라.

제한조건
--------------------
- 0 <= j <= nums[i]
- i + j < n
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000

 

2. 접근 방법

이번 문제는 마지막 인덱스에 모두 도달 가능한 테스트 케이스만 주어지고
마지막 인덱스에 도달하기 위한 최소한의 점프 수를 반환하는 문제이다.

ex) nums = [2,3,1,1,4] 
앞에서부터 갯수를 센다고 가정해보자.

경우의 수 1.
1. 2칸 점프 i = 2, jump = 1
2. 1칸 점프 i = 3, jump = 2
3. 1칸 점프 i = 4, jump = 3

경우의 수 2.
1. 1칸 점프 i = 1, jump = 1
2. 3칸 점프 i = 4, jump = 2

return 최소 점프 수 = 2

여기서 우리는 다음 인덱스로 이동할 때, 
다음 인덱스가 도달할 수 있는 최대 위치가 더 큰 값으로 이동해야 최소 점프수를 구할 수 있다.

즉, 현재 인덱스에서 도달할 수 있는 다음 인덱스 중 i + nums[i] 값이 가장 큰 인덱스로 위치를 이동해야한다.

near = 현재 인덱스에서 점프 가능한 가장 가까운 다음 인덱스(시작)
far = 현재 인덱스에서 점프 가능한 가장 먼 다음 인덱스(끝)

 

 

3. 코드

var jump = function(nums) {
    let near = 0;
    let far = 0;
    let jumps = 0;

    while (far < nums.length - 1) {
        let farthest = 0;
        for (let i = near; i <= far; i++) {
            farthest = Math.max(farthest, i + nums[i]);
        }
        near = far + 1;
        far = farthest;
        jumps++;
    }
    return jumps;
};

 

far 변수가 마지막 인덱스에 도착하기 전이면 반복을 계속 진행한다.

 

현재 인덱스가 도달할 수 있는 다음 인덱스 범위를 near ~ far 사이로 두고,

해당 범위에서 가장 멀리 도달할 수 있는 위치 farthest를 구한다.

 

해당 범위 순회가 끝나면 다음 near는 현재 far 다음 인덱스에서 시작하면 되고,

다음 far는 다음 인덱스가 도달할 수 있는 가장 먼 위치인 farthest를 할당해주면 된다.

 

near, far 가 변경되어 점프를 1 증가 시킨다.

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

반복문이 중첩되었다고 해서 무조건 시간 복잡도가 O(n^2) 것은 아니다.

위 코드에서 while 구문의 종료 조건은 far값이 마지막 인덱스 이상인 경우 종료되는데,

far가 배열의 모든 갯수 만큼 순회하는 것이 아닌 현재 인덱스의 점프 값으로 도달할 수 있는 범위 사이에서 결정되기 때문이다.

 

while 구문 내부에서는 현재 인덱스에 위치한 점프 길이만큼 순회를 돌기 때문에 주어진 배열의 길이만큼 돈다고 말할 수 없다.

 

5.  GPT와 함께 풀기 - 24.10.10 추가

GPT에게 물어봐서 좀 더 이해하기 쉬운 방법으로 접근했다.

var jump = function(nums) {
    let jumps = 0;   // 점프 횟수
    let end = 0;     // 현재 점프의 끝
    let farthest = 0; // 현재까지 갈 수 있는 가장 먼 위치
    
    // 마지막 인덱스 이전까지 순회
    for (let i = 0; i < nums.length - 1; i++) {
        // 가장 멀리 갈 수 있는 위치 갱신
        farthest = Math.max(farthest, i + nums[i]);
        
        // 현재 점프의 끝에 도달하면
        if (i === end) {
            jumps++;         // 점프 횟수 증가
            end = farthest;  // 끝을 가장 멀리 갈 수 있는 위치로 갱신
        }
    }
    return jumps;
};

 

현재 위치에서 도달할 수 있는 최대 점프 위치를 farthest 변수로 설정한다.

각 요소를 순회하면서 farthest를 i + nums[i] 값이 최대인 값으로 갱신한다.

 

현재 인덱스가 도달할 수 있는 가장 먼 위치에 도달했을 때라면 1회 점프 했다고 간주하고

그 사이의 값 중에서 가장 멀리 뛴 곳으로 현재 점프의 끝 위치를 갱신한다.

 

조금 더 부연설명 하자면, 시작인덱스에서 가장 먼 위치에 도달하는 위치를 farthest에 저장해두고,

인덱스가 진행하면서 farthest의 최댓값을 갱신해준다.

단, 인덱스가 end와 동일했을 때 jump를 추가해줌으로써 시작인덱스에서 점프는 1회 한 것으로 인정하고

시작 인덱스에서 가장 멀리 갈 수 있는 값을 저장했으므로 이를 n - 1 인덱스에 도달하기 전까지 반복할 수 있다.

 

반복문이 종료되기 전에 end가 이미 마지막 요소에 도달한 경우가 있으므로 최적화를 할 수도 있다.

하지만 코테를 풀다보니 이런 경우까지 최적화 딱딱 맞춰서 하면서 깔끔한 코드가 나오기 어려운 경우가 많다.

 

최대한 가독성 좋게 이해하기 쉬운 코드를 작성하는 것을 목표로 한다.