문제 링크: https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150
주어진 조건
- nums: 각 요소가 jump 할 수 있는 최대 값을 나타내는 정수 배열
문제
- 만약 마지막 index에 도착할 수 있다면, True 아니면 False를 return 하자
나의 풀이
처음에는 DP를 생각했었다.
따라서 nums=[2, 3, 1, 1, 4]일 경우, index = 0에서 한 칸 점프하는 경우, 두 칸 점프하는 경우 둘 다 고려해서 계산을 해야되므로 재귀함수를 사용해 nums의 마지막 index까지 도달하는 지 계산을 해야하나..? 싶었지만 시간초과였다.
그렇다면, DP가 아니라 한 번의 탐색으로 해결할 수는 없을까 고민하다가 나온 방법의 핵심이 아래 사진이다.
nums = [2, 3, 1, 1, 4] 일 경우를 생각해보자.
nums[i]에서 점프하여 갈 수 있는 칸은 nums[i] ≤ nums[i+1] 가 성립한다면, nums[i+1]에서도 갈 수 있다.
바로 이게 아이디어의 핵심이었다.
구현 코드
class Solution(object):
def canJump(self, nums):
if len(nums) == 1:
return True
if nums[0] == 0:
return False
count = nums[0]
for i in range(1, len(nums)):
count -= 1
if count < 0:
break
if nums[i] >= count and i != len(nums) - 1:
count = nums[i]
return count >= 0
55. Jump Game
-
길이가 1이거나, 첫 번째 요소가 0인 것을 미리 처리
-
count는 현재 점프할 수 있는 최대 길이
-
count를 하나씩 감소시키며 nums 탐색
- count가 0보다 작다면, 더 이상 점프가 불가능하므로 break
- 현재 값이 count보다 값이 크다면, count를 현재 값으로 update
Time: O(n)
Space: O(1)
다른 풀이
class Solution:
def canJump(self, nums: List[int]) -> bool:
last_position = len(nums)-1
for i in range(len(nums)-2,-1,-1):
if (i + nums[i]) >= last_position:
last_position = i
return last_position == 0이전 index에서 마지막 index에 도달하려면 어떻게 해야할까?
→ 바로 index + nums[index] ≥ nums 마지막 index 가 성립하면 된다
위 아이디어를 이용해 이 풀이는 마지막 원소부터 for문을 실행한다.
- nums의 마지막 직전 요소부터 for문 실행
- 만약 nums[i] (현재 index에서 점프할 수 있는 최대 길이)과 i의 합이 last_position보다 크거나 같다 = i에서 점프하면 마지막 위치에 도달 가능
- last_position을 i로 업데이트한다 → i에서는 사실 last_position에 도달할 수 있으므로 업데이트해도 무관
- 계속해서 last_position을 업데이트해주다가 last_position이 0인지 아닌지를 return
⇒ last_position이 0이라는 이야기는 결국, index 0에서 마지막 위치까지 도달 가능하다는 이야기이다!
Time: O(n)
Space: O(1)
이런 DP가 떠오르는 종류의 문제는 넓게 보지말고, 좀 더 좁게 볼 필요가 있는 것 같다. 이전 index에서 마지막 index에 도달하는 방법 이라든가, 이웃한 값의 관계라든가 문제를 작은 문제부터 바라봤으면, 아이디어를 쉽게 떠올렸을 문제인 것 같다.
