[Leetcode]_45. Jump Game 2

문제

길이가 n이고 인덱스가 0인 정수형 배열이 주어진다. 인덱스가 0이므로 초기 위치가 nums[0]이다.

각 요쇼 nums[i]가 의미하는 것은 인덱스 i에서 앞으로 점프할 수 있는 최대 길이를 의미한다.

다시말해서, 너가 nums[i]에 있다면, 너는 nums[i+j]인 어느곳이든 점프할 수 있다.

• 0 <= j <= nums[i]
• i + j < n

nums[n - 1]에 도달하기 위해 최소한의 점프 수를 반환해라.

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

LeetCode - The World's Leading Online Programming Learning Platform

풀이

문제를 어떻게 풀어야할지 막막했다..

그 말인 즉슨 내가 문제를 한국말로도 제대로 이해하지 못하고 있다고 판단하여 문제를 차근차근 한국말로 번역해보면서 이해해보려고 했다.

def jump(nums):
    n = len(nums)
    i = 0
    curr = nums[i]
    count = 0
    
    if n == 1:
        return count
    while True:
        canJump = [i+j for j in range(1,curr+1 if curr < n else n)]
        if n - 1 in canJump:
            count += 1
            break
        maxJump = max(list(map(lambda x: nums[x], canJump))) # 가장 큰 값이 중복일 경우 고려 못함
        curr = maxJump
        i += 1
        count += 1
    return count

 

처음 접근한 방법은 다음과 같다.

• 현재 인덱스에서 점프 가능한 값들을 배열에 담는다.
• 해당 배열 중 n -1이 포함되어 있으면 반복문을 종료하고 count 를 반환한다.
• n - 1이 포함되어 있지 않다면, 해당 배열 요소를 nums에 index로 넣어서 가장 큰 값을 curr 변수에 저장했다.
  • count 를 1 추가한다.

위와 같이 접근한 이유는 현재 위치에서 점프 가능한 위치 중 다음 점프를 할 때 가능한 최대 점프 수가 큰 요소를 다음 점프 시작점으로 하는 것이 n - 1 인덱스에 접근하기 가장 적은 횟수라고 생각했기 때문이다.

하지만 이러한 접근을 했을 때, nums 요소가 같은 값일 경우에 다시 고려해야하는 경우의 수가 많아져서 복잡해진다.

 

그래서 다른사람의 풀이를 참조하였다.

 

def jump(nums):
    count = 0
    end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
    	farthest = max(farthest, i + nums[i])
        if farthest >= len(nums) - 1:
            count += 1
            break
        if i == end:
            count += 1
            end = farthest
    return count

• 가장 멀리 보낼 수 있는 위치를 추적하고 그곳에 도달하는데 필요한 점프 수를 업데이트 한다.
• farthest를 초기 i 와 nums[i]의 합과 기존의 farthest와 비교하여 큰 값으로 갱신한다.
  • 가장 멀리 보낼 수 있는 위치가 n - 1 이상이면, count를 1 추가하고 반복을 종료한다.
  • 그렇지 않으면, count를 1 추가하고 end를 farthest와 동일한 위치로 이동시킨다.
  • 왜냐하면, 각 요소를 순회하면서 가장 멀리 갈 수 있는 위치를 구해야하기 때문에 각 요소가 순회하다가 end와 동일해지는 지점에서만 count를 1 추가해야지만 모든 요소를 순회하면서 최대 점프만 계산에 포함시킬 수 있다.