[알고리즘] LeetCode - Jump Game

Jump Game - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• 인덱스는 첫 번째 자리부터 시작하며, 배열 nums의 각 수는 해당 위치에서의 최대 점프 길이를 나타낸다.
• 마지막 인덱스에 도착할 수 있으면 true, 없으면 false를 반환해야 한다.

문제 해결

• 정수형 변수 dis를 현재 위치에서 가장 멀리 갈 수 있는 위치의 값으로 갱신한다.
• 현재의 위치를 1씩 증가시키면서 dis 보다 작을 때까지 반복해서 최대한 갈 수 있는 거리까지 반복한다.
• 마지막 인덱스까지 갈 수 있는 경우에는 배열의 크기를 초과하고, 갈 수 없는 경우에는 정수형 변수 now가 마지막 인덱스까지 가지 못하고 반복문에 종료된다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public boolean canJump(int[] nums) {
        int dis = 0;
        int now = 0;
        
        while(now <= dis) {
            dis = Math.max(dis, now + nums[now]);
            if (dis >= nums.length - 1) {
                return true;
            }
            now++;
        }
        return false;
    }
}

결과

시간	메모리
2 ms	43.9 MB