Python으로 배열의 마지막 인덱스까지 도달하는 최소 점프 횟수 구하기

모든 요소가 양수인 배열 nums가 있다고 가정해 봅시다. 우리는 현재 인덱스 0에 있으며, 배열의 각 요소는 해당 위치에서 이동할 수 있는 최대 점프 거리를 의미합니다. 목표는 가장 적은 점프 횟수로 마지막 인덱스(n-1, n은 배열의 크기)에 도달하는 것입니다.

예를 들어 배열이 [2,3,1,1,4]라면 출력은 2가 됩니다. 인덱스 0에서 인덱스 1로 점프한 뒤, 다시 인덱스 4(마지막 인덱스)로 점프하면 총 두 번의 점프로 목표에 도달할 수 있기 때문입니다.

문제 해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘을 사용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 점프 범위 내에서 도달 가능한 가장 먼 위치를 계속 추적하는 것입니다.

다음 단계를 따릅니다:

• 세 개의 변수를 초기화합니다: end = 0(현재 점프의 경계), jumps = 0(점프 횟수), farthest = 0(도달 가능한 가장 먼 인덱스)
• i를 0부터 배열 길이 - 1까지 반복합니다:
  • farthest를 farthest와 nums[i] + i 중 더 큰 값으로 갱신합니다.
  • 만약 i == end이고 i가 마지막 인덱스가 아니라면:
    • jumps를 1 증가시킵니다.
    • end를 farthest로 갱신합니다.
• 반복이 끝나면 jumps를 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해할 수 있습니다:

class Solution(object):
   def jump(self, nums):
      end = 0
      jumps = 0
      farthest = 0
      for i in range(len(nums)):
         farthest = max(farthest,nums[i]+i)
         if i == end and i != len(nums)-1:
            jumps+=1
            end = farthest
      return jumps
ob = Solution()
print(ob.jump([3, 4, 3, 0, 1]))

입력

[3, 4, 3, 0, 1]

출력

2

동작 원리 설명

입력 [3, 4, 3, 0, 1]의 경우를 살펴보겠습니다:

• 인덱스 0에서 최대 3칸까지 점프할 수 있으므로 farthest는 3이 됩니다.
• 인덱스 0이 현재 경계(end)와 같으므로 점프 횟수가 1이 되고, 경계가 3으로 갱신됩니다.
• 인덱스 1에서는 4 + 1 = 5까지 도달 가능하므로 farthest가 5로 갱신됩니다.
• 인덱스 3이 경계와 일치하므로 두 번째 점프가 발생하고, 이때 이미 마지막 인덱스에 도달할 수 있습니다.

따라서 결과는 2가 됩니다. 이 알고리즘은 각 위치를 한 번씩만 방문하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.