LeetCode 45(Jump Game II, Python)

1. 문제 링크

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

Jump Game II - LeetCode

2. 문제 설명

• 길이가 n인 정수로 구성된 array인 nums가 주어졌을 때,
  • nums[i]는 i 인덱스로부터 점프할 수 있는 최대 길이를 뜻한다. 즉, 만약 nums[i]에 있다면, 
    • 0 <= j <= nums[i], i + j < n인 nums[i+j]까지 점프할 수 있음을 의미
• 이 때, nums[n-1]에 도달할 수 있는, 최소한의 jumps 수를 반환 (int)
• 예시1)
  • nums = [2,3,1,1,4] 라면, 0 → 1 로 가고, nums[1]은 최대 3 step까지 갈 수 있으므로, 1 → 4로 이동하면 가장 짧게 갈 수 있으므로 2를 반환
• 예시2)
  • nums=[2,3,0,1,4]라고 하면, 0 → 1, 1 → 4로 이동하는게 최소 점프이므로, 2를 반환 

3. 기존 풀이 

• [2,3,1,1,4]를 예시로 생각했을 때, 가장 끝인 4로 바로 올 수 있는 index는 nums[1]과 nums[3]이고,
  • nums[1]이 더 멀리 움직인 것이므로, nums[1] 로 옮기고, 
  • nums[1]로 올 수 있는 값은 nums[0] 뿐이므로, nums[0]으로 이동하며, 이 때마다 count +=1 을 해서, 최종 count를 리턴하였음
• 처음에는 뒤에서부터 앞으로 이동하는게 편하다고 생각했는데,
  • 볼 필요가 없는 앞단계까지도 추적을 하게 되서, 비효율이 생기고, runtime이 좋지 않았음. (하위 30%..)

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        start = len(nums)-1
        count = 0

        while start > 0:        
            for i in range(start): 
                if nums[i] + i >= start:
                    count += 1
                    break # 가장 작은 i를 불러옴
            start = i 
        
        return count

 

• 앞에서부터 추적하는 풀이 (by 제로_콜라)
  • 기본 개념은 동일. "한 번 갈 때 최대한 멀리 가야하며, 출발 위치가 멀수록 좋음" 
  • 현재 위치에서 갈 수 있는 위치 i에 대해 i + nums[i]가 그 다음 갈 수 있는 실제 거리이고, 이 값이 최대가 되는 i로 이동하면서 cnt를 1씩 증가시키는 구조. 그러다가, 현재 위치에서 도착지점에 갈 수 있게 되면 지금까지의 cnt를 리턴

class Solution:
    def jump(self, nums: List[int]) -> int:
        start = 0
        how_far = {}
        cnt = 0
        end = len(nums)-1

        while start < end:                 #예시[2,3,1,1,4]
            for i in range(nums[start]+1): #i가 0, 1, 2
                temp = start + i           #temp가 0, 1, 2(start=0)
                if temp < end:
                    step = temp + nums[temp] #step이 2,4,3
                    how_far[step] = temp     #{2:0, 4:1, 3:2}
                else:
                    cnt += 1
                    return cnt
            
            start = how_far[max(how_far)] #max는4, how_far[4]=1이므로 start=1로 변
            how_far = {}
            cnt += 1
            
        return cnt

 

4. 다른 풀이

• 한 번 이동하여 가장 멀리갈 수 있는 지점을 정하며, 지점에서 가장 멀리갈 수 있는 지점을 업데이트 하면서, 
  • 도착 지점으로 갈 수 있으면 반환,
  • 그렇지 않으면 계속 한 칸씩 이동하다가, 한 번 이동해서 갈 수 있는 가장 먼 지점에 도착하면 이동횟수를 올리고,
  • 두번 이동하여 가장 멀리갈 수 있는 지점을 정하는 것을 반복
• 레벨(이동횟수)에 따라 조회하므로 BFS 방식
• [2,1,1,1,4]로 예시를 작성해보면,
  • [2]에서 출발하면 [2,1,1]까지 가능하고 (1번 이동)
  • [1]에서 출발하면, [2,1,1]까지 가능하고 도착지점은 불가 (1번 이동)
  • 그 다음 [1]에서 출발하면 일단 1번 이동하여 가능한 최대 위치까지 왔으므로 1번 더 이동해야 하며, [2,1,1,1]까지 가능 (2번 이동)
  • 그 다음에 [1]에서 출발하면 2번 이동하여 가능한 최대 위치까지 왔으므로 1번 더 이동하고 [2,1,1,1,4]까지 가능하며 도착 (3번 이동)

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0        # 결과적으로 반환할 최소 점프 횟수
        end = 0        # 현재 레벨에서의 마지막 인덱스
        farthest = 0   # 현재 레벨에서의 최대 이동 거리

        # BFS(너비우선 탐색)
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])

            # 만약 최대 이동 거리가 배열의 마지막 인덱스보다 크거나 같다면 목표 지점에 도달할 수 있음
            if farthest >= len(nums) - 1:
                ans += 1
                break

            # 현재 인덱스가 현재 레벨에서의 마지막 인덱스와 같다면 다음 레벨로 넘어감
            if i == end:
                ans += 1        # 레벨 증가
                end = farthest  # 다음 레벨의 마지막 인덱스 갱신

        return ans

 

5. 배운 점 

• BFS 방식에 익숙해지기. DFS 방식에 비해 메모리 사용량은 많을 수도 있고, 시간 복잡도는 같지만, 실제로는 더 빠른 경우가 많음.