45. Jump Game II

문제링크: https://leetcode.com/problems/jump-game-ii/

nums의 배열은 해당 칸에서 갈 수 있는 최대 점프다. 마지막 칸에 다다르기 위해 필요한 최소 점프 수를 구해야 한다.

Solution

1. Dynamic programming

앞에서부터 현재 칸에 도달하는 최소 점프 수를 기록한다.

b <= nums[a] 일 때 즉 a에서 한번의 점프로 a + b에 도달할 수 있을 때
minCount[a + b] = minCount[a] + 1

이를 앞에서부터 반복하면 마지막 minCount의 값이 결과가 된다.

Algorithm

• 현재 칸이 바로 마지막일 경우는 고려하지 못하므로 0을 바로 반환한다.
• minCount 배열을 nums의 크기만큼 선언한다.
• 앞에서부터 curIdx로 반복한다.
• myCount는 curIdx에 도달하기 위한 최소 카운트다.
• 현재 좌표에서 다음 점프로 끝에 도달할 수 있는 경우 결과를 반환한다.
• 위의 점화식으로 도달 가능한 좌표에 minCount[curIdx] + 1을 저장한다.

var jump = function(nums) {
  // Get count;
  // DP with count;
  if (nums.length === 1) return 0;
  const minCount = new Array(nums.length).fill(0);
  for (let curIdx = 0; curIdx < nums.length; curIdx++) {
    const myCount = minCount[curIdx];
    if (nums.length - 1 <= curIdx + nums[curIdx]) return myCount + 1;
    
    for (let i = 1; i <= nums[curIdx]; i++) {
      if (curIdx + i === nums.length) break;
      if (minCount[curIdx + i] === 0) {
        minCount[curIdx + i] = myCount + 1;
      }
    }
  }
  
};

시간/공간 모두 O(n)의 복잡도를 사용한다.

2. Greedy

위의 memoization에 사용한 minCount배열은 구간별로 적용되는 정보다. 따라서 모든 iteration에서 필요한 정보가 아니라 점프 별로 최대 이동 가능한 좌표가 있고 이는 점점 갱신되는 데이터로 현재 점프의 최대값과 다음 점프의 최대 값만을 통해 답을 구할 수 있다.

Algorithm

• 현재 점프의 최대좌표를 curMax, 다음 점프의 최대좌표를 nextMax, 다음 점프를 포함한 점프 수를 count라 하자.
• 반복을 통해 nums를 탐색한다.
• 현재 좌표가 curMax를 초과했을 때, 즉 다음 점프로 가야하는 곳이면 count를 증가시키고 curMax를 nextMax로 갱신한다.
• nextMax는 현재 갈 수 있는 최대 좌표 i + nums[i]와 비교해 갱신한다.
• 루프를 탈출하는 조건(다음 점프로 목표 도착 가능) 할때 count(다음 점프를 포함한 점프 수)를 결과로 반환한다.

var jump = function(nums) {
  // greedy
  let curMax = -1;
  let nextMax = 0;
  let count = 0;
  const target = nums.length - 1;
  for (let i = 0; nextMax < target; i++) {
    if (i > curMax) { 
      count++;
      curMax = nextMax;
    }
    nextMax = Math.max(nextMax, i + nums[i]);
  }
  return count;
};

1번에서 memoization으로 쓰였던 부분을 임시 데이터로 변경하여 공간복잡도를 O(1)로 크게 개선시켰다.