55. Jump Game

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

nums 배열에는 각 지점에서 가능한 최대 점프 거리를 나타낸다. 마지막 지점에 도착할 수 있는지 알아내는 문제다.

Solution

Greedy

최대로 멀리 갈 수 있는지 확인하기 위해선 O(n)의 시간복잡도는 필연적이다. 맨 앞부터 고려하면 i + nums[i]로 현재 갈 수 있는 최대 거리를 알 수 있고 갱신할 수 있다. 최대 거리에 도착지점보다 먼저 다다를경우 false, 도착지점에 도착하면 true를 반환한다.

Algorithm

• goal 은 도착지점의 좌표다.
• 최대거리는 처음에 0, nums를 탐색하면서 i + nums[i]가 최대거리보다 클 경우 최대거리를 갱신한다.
• 중간에 maximum 보다 goal이 클 경우 도착 가능하므로 true를 반환한다.
• maximum좌표에 도달햇는데 아직 goal에 도착하지 못했다면 false를 반환한다.

var canJump = function(nums) {
  const goal = nums.length - 1;
  let maximum = 0;
  for (let i = 0; i <= maximum; i++) {
    if (maximum >= goal) return true;
    maximum = Math.max(maximum, i + nums[i]);
  }
  return false;
};