[LeetCode] 55. Jump Game (C++)

문제

 

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

Jump Game - LeetCode

 

풀이

 

난이도: Medium 

 

DP풀이

일단 가장 생각하기 쉬운 다이나믹 프로그래밍 풀이부터 소개하겠다.

dp[idx]에 idx에서부터 마지막까지 도달할 수 있는 지 여부를 저장한다.

 

dp[end]만 true로 설정하고 뒤에서부터 배열을 순서대로 확인해본다.

idx에서는 1~nums[idx]까지 점프할 수 있으므로 dp[idx + (1~ nums[idx])]중에서 true가 있다면 마지막까지 도달할 수 있다.

 

 

 

이런 알고리즘은 공간복잡도 O(n), 시작 복잡도 O(n*m)가 소요된다.

이보다 공간과 시간 복잡도를 훨씬 줄일 수 있는 스위핑 알고리즘이 있다.

 

 

 

스위핑 풀이

 

스위핑 풀이는 앞에서부터 배열을 순차적으로 진행한다.

현재 위치 idx에서 가장 멀리 점프하여 도달할 수 있는 곳은 idx + nums[idx]이다.

idx를 앞으로 진행하면서 가장 멀리 도달할 수 있는 위치를 reached에 저장하자.

만약 idx가 reached보다 크다면 이전의 위치들에서는 idx에도달 할 수 없다는 의미가 된다.

 

예를 들어 [1, 1, 0, 4]에서는 다음과 같이 진행된다.

idx: 0 reached: 1

[1, 1, 0, 4]

 

idx: 1 reached: 2

[1, 1, 0, 4]

 

idx: 2 reached: 2

[1, 1, 0, 4]

 

idx: 3 reached: 2 => idx > reached!

[1, 1, 0, 4]

 

따라서 idx가 배열의 끝까지 진행되는 경우만 마지막에 도달할 수 있다.

 

풀이 참조: Linear and simple solution in C++