[LeetCode][Greedy] 55. Jump Game

 

문제 링크

 

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

Jump Game - LeetCode

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

 

Return true if you can reach the last index, or false otherwise.

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

 

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. 
Its maximum jump length is 0, which makes it impossible to reach the last index.

 

 

 

문제 해석

 

매번 느끼는 거지만 LeetCode 문제는 description은 참 군더더기없이 깔끔하다 ;P

한 문장으로 설명하면 "배열의 처음에서 끝까지 갈 수 있니?"

배열의 first index에 위치하며 각 원소의 값은 해당 index에서 움직일 수 있는 최대 거리를 의미한다.

 

index를 제일 적게 방문해야한다 등의 조건 없이 그저 갈 수 있는지에 대한 여부만 체크하는 문제!

n과 n+1과의 관계를 찾아볼까? 예외는 없을까? 짱구를 굴려보았지만

이 문제는 조금 더 탐욕스럽게 접근해도 될 듯 하다.

 

바로 Greedy Algorithm!

 

대신 방향을 앞에서 뒤로 확장하는 것이 아니라 뒤에서 앞으로 축소하는 것으로 생각해 볼 것.

원소의 개수를 N이라 하면, 아래와 같이 생각해 보자!

• Yes → 그럼 N-2번째에서 N-1번째로 갈 수 있어?
• No → 그럼 N-2번째에서 N번째로 갈 수 있어?

 

 

 

 

제출 코드

 

class Solution {
    public boolean canJump(int[] nums) {
        
        int last = nums.length - 1;
        
        for (int i = last - 1; i >= 0; i--) {
            if ((i + nums[i]) >= last) last = i;
        }
        
        return (last == 0);
    }
}

 

 

 

 

제출 결과

 

 

 

 

참고 링크

 

• https://blog.naver.com/ndb796/221242106787
• https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

 

 

 

 

 

Greedy Algrorithm에 대한 자세한 설명은

to be continued! >"<

 

- mushroong

 

 

 

 

---