๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค.
๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python์ ์ฌ์ฉํฉ๋๋ค.
๋์ด๋: Medium
ํค์๋: Array, DP
๋ฌธ์
๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150
์ ์ํ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์. ๋น์ ์ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ index์ ์์นํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์์น์์๋ถํฐ ๋น์ ์ด ์ต๋๋ก ์ ํํ ์ ์๋ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ด ๋, ๋ง์ง๋ง index ์ ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ true, ์๋ ๊ฒฝ์ฐ false๋ฅผ ๋ฐํํ๋ผ.
์์ ์ ๋ ฅ
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
๋ฌธ์ ํ์ด
ํ์ด 1. DP (Top-down approach)
๋ฌธ์ ์์ ๊ฐ๋ฅ์ฑ ์ฌ๋ถ๋ฅผ ๋ฌผ์ด๋ณด๊ณ ์๊ณ , ์ด ๋ ๋ช ๋ฒ์งธ index๋ฅผ ์ ํํ๋๋์ ๋ฐ๋ผ ๋ง์ง๋ง index์์ ๋๋ฌ ์ฌ๋ถ๊ฐ ๋ฌ๋ผ์ง ์ ์์ผ๋ฏ๋ก Dynamic Programming์ ์ฌ์ฉํด์ ๋ฌธ์ ๋ฅผ ํ๊ณ ์ํ๋ค. ์ฐ์ , ๋ณ๋์ ์ต์ ํ ์์ด ๊ฐ์ฅ ๊ฐ๋จํ๊ฒ ๊ตฌํํ ์ ์๋ Top-Down approach๋ฅผ ์ฌ์ฉํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
1) ์ข ๋ฃ ์กฐ๊ฑด์ ๋ง์ง๋ง index์ ๋๋ฌํ๋๊ฒฝ์ฐ return True
2) ๊ทธ ๋ค์ state๋ ํ์ฌ ์์น i์์๋ถํฐ ์ฌ๋ผ๊ฐ ์ ์๋ ์ต๋ ๋์ด๊น์ง์ ๊ฐ๊ฐ์ ์์น์์ ๋๋ฌ ๊ฐ๋ฅํ ์ฌ๋ถ ํ์
-> ํ๋๋ผ๋ ๋๋ฌ ๊ฐ๋ฅํ๋ฉด return True
-> ๋ชจ๋ ์กฐํํด๋ณด๊ณ ๋ถ๊ฐ๋ฅํ๋ฉด return False
์ด๋ฅผ ์ข ํฉํด์ ๊ตฌํํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
class Solution:
def canJump(self, nums: List[int]) -> bool:
@cache
def dp(i):
if i >= len(nums)-1:
return True
for j in range(i+1, i+nums[i]+1):
if dp(j):
return True
return False
return dp(0)
๐ฐ Runtime 5495 ms
๐ป Memory 56.1 MB
ํ์ด 2. DP (Bottom-up approach)
์ฌ๊ท ํจ์๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์ 1์ ์๋ฌด๋๋ overhead๋ก์ธํด ์๋๊ฐ ๋๋ฆฌ๋ค. ์ด๋ฅผ ๊ฐ์ ํ๊ธฐ ์ํด์ recursion์ array ์ํ๋ก ๋์ฒดํ๋ ๊ฒ์ด ํ์ํ๋ค. ๋ฐ๋ผ์, ๋ฐฉ์ 1์ ์ข ๋ฃ์กฐ๊ฑด์์๋ถํฐ ์ญ์ผ๋ก 0 index๊น์ง ๋๋ฌ์ด ๊ฐ๋ฅํ์ง ์ฌ๋ถ๋ฅผ ํ์ธํ๋๋ก ์ฝ๋๋ฅผ ์์ฑํด๋ณด์๋ค.
class Solution:
def canJump(self, nums: List[int]) -> bool:
N = len(nums)
if N == 1:
return True
dp = [False] * N
# basecase
dp[-1] = True
for i in range(len(nums)-1,-1,-1):
for j in range(i+1, min(i+nums[i]+1, N)):
if dp[j]:
dp[i] = True
break
return dp[0]
๐ฐ Runtime 2499 ms
๐ป Memory 17.5 MB
ํ์ด 3. DP (Bottom-up approach) ๋ณํ
DP ์๊ณ ๋ฆฌ์ฆ์์ ๊ตณ์ด ์ ์ฒด dp์ ๋ํ ์ํ๋ฅผ ํด์ค ํ์๊ฐ ์๋ค. ์ต๋ ์ต์ ๊ฐ์ ๋ฌป๋๊ฒ์๋๋ผ ๊ทธ๋ฅ ๊ฐ๋ฅ์ฑ์ ๋ฌผ์ด๋ณด๋๊ฒ์ด๊ธฐ๋๋ฌธ์. ๊ทธ๋์ ๋ชฉ์ ์ง (top)๋ฅผ ๋งค๋ฒ ๊ฐฑ์ ํด์ฃผ๊ณ ํ์ฌ step์์ ๋ชฉ์ ์ง์ ๋๋ฌ ๊ฐ๋ฅํ์ง ์ฌ๋ถ๋ฅผ ํ๋จํ๋๋ก ์ฝ๋๋ฅผ ์์ ํ์๋ค.
class Solution:
def canJump(self, nums: List[int]) -> bool:
N, top = len(nums), len(nums)-1
for i in range(N-2,-1,-1):
if (i + nums[i] >= top):
top = i
return True if (top == 0) else False
๐ฐ Runtime 384 ms
๐ป Memory 17.5 MB
'IN DEPTH CAKE > Supercoder' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ฝ๋ฉ/LeetCode150-(11)] 274. H-Index (2) | 2023.08.23 |
---|---|
[์ฝ๋ฉ/LeetCode150-(10)] 45. Jump Game II (0) | 2023.08.22 |
[์ฝ๋ฉ/LeetCode150-(8)] Best Time to Buy and Sell Stock II (122) (0) | 2023.08.22 |
[์ฝ๋ฉ/LeetCode150-(7)] Best Time to Buy and Sell Stock (121) (0) | 2023.08.20 |
[์ฝ๋ฉ/LeetCode150-(6)] Rotate Array (189) (0) | 2023.08.20 |