
๐ก ์๊ฐ ๋ฐฉ์
๋น์ฅ ์๋ index์์ ์ ์ผ ๋ฉ๋ฆฌ ๋๋ฌํ ์ ์๋ index๊ฐ ๋ญ์ง ์ผ๋จ ๋ณธ๋ค
๊ทธ๋ฆฌ๊ณ loop์ ๋๋ ค์ ๋ง์ง๋ง๊น์ง ๋์ฐฉํ ์ ์๋์ง ์ฝ๋๋ฅผ ์ง๋ณธ๋ค
๐ป ์ฝ๋
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
max_reachable = 0
for i in range(n):
if i > max_reachable:
return False
elif max_reachable == n:
return True
max_reachable = max(max_reachable, i + nums[i])
return True
* max_reachable = 0 [์ต๋ ๋๋ฌ ๊ฐ๋ฅํ index]
* if๋ฌธ ์ค๋ช
๋ง์ฝ์ ํ์ฌ ๋ด๊ฐ ์๋ index๊ฐ ํ์ฌ๊น์ง ์ต๋ ๋๋ฌ ๊ฐ๋ฅํ index์ธ max_reachable๋ณด๋ค ํฌ๋ค๋ฉด, ํ์ฌ ์์น๋ ์ ์ ์ ํ๋ก ๋๋ฌ์ด ๋ถ๊ฐ๋ฅํ๋ค, ๊ทธ๋ฌ๋ฏ๋ก False๋ฅผ ๋ฆฌํดํด์ฃผ๋ฉด ๋๋๋ค
๋๋, ๋ง์ฝ loop๋ฅผ ๋ค ๋๋ฆฌ๊ธฐ ์ ์ ๋ง์ง๋ง๊น์ง ๋๋ฌํ ์ ์์ผ๋ฉด True๋ฅผ ๋ฆฌํดํด์ฃผ๊ณ ๋๋๋ค. ์ด๋ ๊ฒ ํ๋ค๋ฉด ํจ์จ์ด ์ข ๋ ์ข์์ง๋ค๊ณ ์๊ฐํ๋ค. ์? ๋ง์ฝ ์ด๋ฏธ ๊ฐ๋ฅํ๋ค๋ ์ ๋ต์ด ๋์๋ค๋ฉด ๊ตณ์ด ๋๋จธ์ง๋ฅผ ๋๋ฆด ํ์๊ฐ ์๊ธฐ ๋๋ฌธ์ (๋ฐ์ ์์ ์ฐธ๊ณ )
* max_reachable = max(max_reachable, i + nums[i]) ์ค๋ช
์ต๋ ๋๋ฌ ๊ฐ๋ฅํ index -> max_reachable๋ฅผ ์ ๋ฐ์ดํธํด์ค๋ค
์ด๊ฒ ๋ฌด์จ ๋ง์ธ์ง๋ ๊ทธ๋ฆผ์ผ๋ก ์ค๋ช ํ๋ ๊ฒ ์ข์ ๊ฒ ๊ฐ๋ค

ํ์ฌ max_reachable = 2์ด๋ค.
๊ทธ๋ฆฌ๊ณ ๋ณด๋ค์ํผ index 2์ธ 0์ด๋ผ๋ ์ซ์๊น์ง ๊ฐ ์ ์๋ค
์ฌ๊ธฐ์ ์ฐ๋ฆฌ๊ฐ 2๋ฒ์งธ ๋ฃจํ ์ฆ i = 1์ ๋๋ฆด ๋, ์ฐ๋ฆฌ๋ index 1์์ 3์ ์ ํํ ์ ์๋ค๋ ๊ฒ์ ํ์ธํ ์ ์๋ค. ์ฆ 4๋ฒ index๊น์ง ๊ฐ ์ ์๋ ์ ์ด๋ค.
๊ทธ๋ฌ๋ ์ฐ๋ฆฌ๊ฐ ๋๋ฌ ๊ฐ๋ฅํ index๋ 4๋ฒ ์ฆ ๋ง์ง๋ง index์ธ 5์ด๋ค. (index 0 -> 1 -> 4, ๋)

โญ๏ธ๋ค๋ฅธ ๋ฐฉ๋ฒ
https://www.youtube.com/watch?v=Yan0cv2cLy8&ab_channel=NeetCode
์ด ์ ํ๋ฒ์ ๊ฒฝ์ฐ ๋ฐฐ์ด์ ๋ค์์ ์์ํด์ ๋ง์ง๋ง์ ๋๋ฌํด์ผ ํ๋ index๋ฅผ ์ ์ฐจ ์์ผ๋ก ๋น๊ธฐ๋ ๋ฐฉ๋ฒ์ด๋ค
์ด๋ค ์ํฉ์์ ๋ค์์ ์์ํ๋ ๊ฒ ์ข์์ง ๋ชจ๋ฅด๊ฒ ์ง๋ง ๋ ๋ด ์ฝ๋์ ์ ๊ทผ ๋ฐฉ์์ด ์ข ๋ ์ง๊ด์ ์ด๋ผ๊ณ ์๊ฐํ๋ค
์ฌ๋ด์ผ๋ก ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ ์ false๊ฐ ๋์ค๋ ๊ฐ๋จํ test case๋ฅผ ๋จผ์ ๋ง๋๋ ์ต๊ด์ด ์๋๋ฐ ์ผ๋จ์ ์ด๋ฐ ์ฌ๊ณ ๋ฐฉ์์ด ๋๋ ๋ฌธ์ ๋ฅผ ํ ๋ ๋ ๋์์ด ๋๋ ๊ฒ ๊ฐ๋ค.
'์ฝ๋ฉ ํ ์คํธ > leetcode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| 104. Maximum Depth of Binary Tree (Easy) [Java] (1) | 2024.02.09 |
|---|---|
| 226. Invert Binary Tree (Easy) [Java] (0) | 2024.02.09 |
| 53. Maximum Subarray (Medium) [Python] (0) | 2024.02.04 |
| 746. Min Cost Climbing Stairs (Easy) [Python] (0) | 2024.02.04 |
| 70. Climbing Stairs (Easy) [Python] (2) | 2024.02.03 |