Climbing Stairs
https://leetcode.com/problems/climbing-stairs/ (opens in a new tab)
내 풀이
Tree
왜 Tree를 썻는지는 묻지마라 그냥 생각나는 풀이가 이것밖에 없었다.
시간 초과로 실패했다.
class TreeNode :
def __init__(self, val, left = None, right = None) -> None:
self.val = val
self.right = right
self.left = left
from collections import deque
class Solution :
def climbStairs(self, n: int) -> int:
q = deque()
q.append(TreeNode(n - 1))
q.append(TreeNode(n - 2))
cnt = 0
while q :
cur_node: TreeNode = q.popleft()
cur_value = cur_node.val
if cur_value == 0 :
cnt += 1
if cur_value >= 1 :
cur_node.left = TreeNode(val=cur_value - 1)
q.append(cur_node.left)
if cur_value >= 2 :
cur_node.right = TreeNode(val=cur_value - 2)
q.append(cur_node.right)
return cnt단순 반복문으로 풀려고 한거
시간 초과로 실패함
from collections import deque
class Solution :
def climbStairs(self, n: int) -> int:
cnt = 1
q = deque()
q.append(n)
cnt = 0
while q :
cur_val = q.popleft()
if cur_val - 1 >= 0 :
if cur_val - 1 == 0 :
cnt += 1
continue
q.append(cur_val - 1)
if cur_val - 2 >= 0 :
if cur_val - 2 == 0 :
cnt += 1
continue
q.append(cur_val - 2)
return cnt해설
문제 해결의 핵심적인 아이디어는 n 번째 계단은 n - 1 번째 계단에서 1칸을 올라가거나, n - 2 번째 계단에서 2칸을 올라가는 방법으로 구할 수 있다는 것이다.
이를 통해서 n 번째 계단은 n - 1 번째 계단의 방법의 수와 n - 2 번째 계단의 방법의 수를 더한 것과 같다는 것을 알 수 있다.
Top Down (recurssion)
memory = {}
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1 :
return 1
if n == 2 :
return 2
if n not in memory.keys() :
memory[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
return memory[n]bottom up
memory = {}
class Solution:
def climbStairs(self, n: int) -> int:
memory[1] = 1
memory[2] = 2
for i in range(3, n + 1) :
if i not in memory.keys() :
memory[i] = memory[i - 1] + memory[i - 2]
return memory[n]