[리트코드] 45. Jump Game II

문제

https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

---

✔ 문제접근 #1 완전탐색[통과] ⭕

Intuition
완전탐색을 통해 dist라는 최소 이동 횟수 배열에 최솟값을 갱신해 나간다.

Algorithm

배열을 순회하면서, 현재 배열값부터 점프할 수 있는 거리까지 한 번 더 순회하면서 dist 배열에 최솟값을 갱신해 나간다.

def jump(self, nums: List[int]) -> int:
    # 처음에는 index 0의 위치에 있다.
    # num[i]는 index i로부터 점플할 수 있는 최대값을 나타냄
    # 오른쪽 끝에 다다를 수 있는 최소 점프횟수를 반환해라
    # 항상 도달할 수 있는 경우만 주어진다

    n = len(nums)

    MAX_INT = sys.maxsize
    dist = [MAX_INT] * n
    dist[0] = 0

    for i in range(n):   
        jump = nums[i]
        for j in range(i + 1, min(i + jump + 1, n)):
            dist[j] = min(dist[j], dist[i] + 1)

    return dist[n - 1]

 

일단은 통과..

Complexity Analysis

• 시간 복잡도 : O(N**2)
  • nums 배열을 이중탐색 O(N**2)
  • 그러므로 전체시작복잡도 : O(N**2)

• 공간복잡도 : O(N)
  
  • 최소거리값을 저장하기위한 dist 리스트 사용

 

 

✔ 문제접근 #2 그리디(솔루션 분석)

-> 아래의 기타풀이 및 회고

---

기타 풀이 및 회고

주어진 배열 길이가 최대 10**4이었기 때문에 2중 포문을 사용한다면 시간복잡도에서 조금 위험할 것 같다고 생각하였다. 다른 풀이가 떠오르지 않아 일단 완전탐색으로 풀이하였는데 통과를 하긴 하였다. 두둥..

 

Jump Game 1 문제에서도 조금 헤맸었는데 이 문제에서도 조금 많이 헤맸다.

우선은 또다른 풀이법들을 찾아보았다.

 

1. 그리디 방법으로 O(n)의 시간복잡도에 해결한다?! 

우선은 정답코드인데 한 번에 확 이해가 가지 않는다. -> 분석 중.. 

def jump(self, nums: List[int]) -> int:
    pre = 0
    jump = 0
    far = 0

    for i in range(len(nums)-1):
        far = max(far, nums[i] + i)            

        if i == pre:
            jump += 1
            pre = far


    return jump

코드를 분석하려 들면은 단순 구현이기 때문에 이해가 잘 안 갈 수 있다. 핵심아이디어를 이해하고 구현해 보자.

핵심아이디어

 

위의 그림을 보면 첫 번째 2의 값에서 점프로 갈 수 있는 영역을 파란색 영역으로 색칠하였다. 그래서 저 파란 영역으로 점프할 때 jump값이 + 1 된다. 그다음에는 저 파란색 영역 안에서 점프를 하게 될 텐데, 파란색 영역에서 점프를 했을 때 갈 수 있는 최대 범위가 초록색 범위이다. 즉 두 번째 점프는 파란색 영역에서 점프를 한다고 했을 때 적어도 초록색 영역 중에 하나로는 점프를 해야 한다. 이렇게 jump 2번을 하게 되면 마지막 위치로 점프할 수 있기 때문에 jump == 2가 정답이 된다.

 

요약 : 빨간 영역에서 뛸 수 있는 다음 영역은 파란 영역이다. 파란 영역에서 뛸 수 있는 다음 영역은 초록 영역이다. 총 2번!

 

역시 그림이 최고야..

 

이러한 아이디어를 코드로 구현한 게 위에 있는 코드이다. pre는 현재 탐색하고 있는 영역의 마지막 칸 인덱스를 나타낸다. 그래서 i값이 pre에 도착하게 되면 영역 탐색을 다 마쳤다고 간주하고 jump+1을 해주게 된다. 그리고 far는 다음 영역에서 갈 수 있는 최대 거리이다. pre를 far에 설정하고 다시 한번 i부터 pre까지 현재 영역을 탐색하며 far값을 통해 다음 영역을 갱신해 나간다.( 이 부분은 핵심 아이디어를 제대로 이해했다면..!? 이해할 수 있을 것이다)

 

 

간만에 그리디 문제를 풀면서 뇌자극 제대로 됐다 ):

머리가 안 굴러가는데(?) dp, 그리디에 호되게 당하고 싶지 않다면 익숙함, 복습, 반복이 답인것같다.