[LeetCode] 55. Jump Game

https://leetcode.com/problems/jump-game

개요

1. 정수 배열 nums가 제공된다. 배열의 각 원소는 해당 위치에서 최대 점프할 수 있는 길이이다.
   • 인덱스 + 원소 = 최대 이동 가능한 인덱스
2. 마지막 인덱스에 도달할 수 있는가?

문제 해결 아이디어

• 케이스 비교
  • 마지막 인덱스 도달 가능 : [2, 3, 1, 1, 4]
    
    ➡️ 이동 가능한 범위 내에 4가 있다.
    • 0 에서 1 로 이동 가능하다.
    • 1 에서 4 까지 이동 가능하다.
  • 마지막 인덱스 도달 불가 : [3, 2, 1, 0, 4]
    
    ➡️ 어떤 이동 가능한 범위 내에도 4가 없다.
    • 0에서 1로 이동 가능하다.
    • 1에서 4로 이동 불가하다.

🧐 이동할 수 있는 인덱스 범위인지 검사하자

➡️ 이동할 수 있는 경우의 수가 있는지, 즉 가능성을 범위로 표현할 수 있다.

의사 코드

1. 주어진 배열을 돈다
2. 이동 가능한 최대 인덱스와 현재 인덱스를 검사한다.
   2-1. 이동 가능한 최대 인덱스가 현재 인덱스보다 작다.
   2-1-1. 이동할 수 없다.
3. 현재 인덱스에서 이동 가능한 인덱스를 계산한다.
4. 이동 가능한 최대 인덱스와 현재 인덱스의 이동 가능한 인덱스를 비교한다.
   4-1. 이동 가능한 최대 인덱스보다 현재 인덱스의 이동 가능한 인덱스가 크다.
   4-1-1. 이동 가능한 최대 인덱스 = 현재 인덱스의 이동 가능한 인덱스
5. 모든 원소를 무사히 통과했다면, 이동 가능하다.

최대 이동 가능 인덱스 = 0
for(인덱스 = 0 to 주어진 배열의 길이){
	if(인덱스 > 최대 이동 가능 인덱스){
    	return false
    }
    if(현재 이동 가능 인덱스 > 최대 이동 가능 인덱스){
    최대 이동 가능 인덱스 = 현재 이동 가능 인덱스}
    }
    return true

결과

전체 코드 github 링크

다른 풀이

public boolean canJump(int[] nums) {
       int reachable = 0;
       for(int i = 0; i < nums.length; i ++) {
           if(i > reachable) return false;
           reachable = Math.max(reachable, i + nums[i]);
       } 
       return true;
    }

나의 코드와 동일하다.
Math.max(a, b) 를 활용하면 if문 없이도 바로 최대값을 갱신할 수 있다.