[LeetCode#55] Jump Game

❒ Description

---

날짜	2024.09.15 (일)
난이도	Medium
제목	Jump Game
링크	https://leetcode.com/problems/jump-game/description/
자료구조 / 알고리즘	배열 / 그리디
시간 복잡도	O(n)

 

이번 문제는 Greedy 알고리즘을 사용해서 해결하는 문제다. 처음에 재귀를 통해 접근을 했지만 풀지 못했고,

풀었다고 하더라도 Time Limie Exceeded 에러를 만나게 된다. 

 

 

 

 

 

 

❒ Greedy(탐욕적) 알고리즘

---

Greedy 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은

순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용 했을 때 만족시킬 수

있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

 

 

 

 

❒ 문제 분석

---

이 문제는 마지막 index까지 도달할 수 있냐 없냐를 확인해야 하는 문제이다. 배열 `{2, 3, 1, 1, 4}`이 주어졌을 때,

1번 째 index는 최대 2칸을 갈 수 있다. 여기서 최대 2칸이라고 했기 때문에 index#1도 갈 수 있고, index#2 도

갈 수 있다는 의미이다.

 

풀이 순서

1. 최대로 도달할 수 있는 값을 담는 reachable 선언
2. 배열 순회
   • 현재 index > reachable : 그 index에는 도달할 수 없다.
   • 현재 index =< reachable : 도달할 수 있는 최대 index 갱신 

 

 

 

 

 

❒ Solution

---

1. Greedy 알고리즘

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;
}

 

 

 

2. Recursive

public boolean canJump(int[] nums) {
   canJumpFromPosition(0, nums);
}

public boolean canJumpFromPosition(int position, int[] nums) {
    if (position == nums.length - 1) {
        return true;
    }
    int reachable = Math.min(position + nums[i], nums.length - 1);
    for (nextPositsion = position + 1; nextPosition <= reachable; nextPosition ++) {
        if (canJumpFromPosition(nextPosition, nums) {
            return true;
        }
    }
    return false;
}

 

 

 

 

 

---