(Leetcode) 70 - Climbing Stairs
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/climbing-stairs/description/
이 문제는 DP 문제이다.
처음의 접근 방법
처음에는 아래와 같이 작성하였다.
class Solution:
def climbStairs(self, n: int) -> int:
return self.select(1, n) + self.select(2, n)
def select(self, step, left) -> int:
if left < step:
return 0
if left == step:
return 1
left = left - step
return self.select(1, left) + self.select(2, left)
문제는 풀리긴 한다. 그런데 n 값이 커질수록 시간이 엄청나게 늘어나게 된다. 그래서 수정이 필요하였다.
최종 접근 방법
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.calc(n)
def calc(self, n: int) -> int:
dict = {}
dict[1] = 1
dict[2] = 2
for i in range(3, n + 1):
dict[i] = dict[i-1] + dict[i-2]
return dict[n]
그래서 규칙을 찾아 위와 같이 수정하여 통과하였다.
규칙성만 찾으면 풀 수 있는 문제이기 때문에 따로 정리는 하지 않는다.
펜으로 경우의 수를 찾아가면서 풀었는데 뭔가 수능 수학을 다시 푸는 기분이 들었다.
시간복잡도
n 번의 반복이 진행됨
O(n) 의 시간 복잡도를 가짐
공간복잡도
dict 에 n 까지의 방법의 수를 저장함
O(n) 의 공간 복잡도를 가짐
자바로 다시 풀어보기 (24.05.15)
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
}
int result = 0;
int temp1 = 1, temp2 = 2;
for(int i = 3; i <= n; i++) {
result = temp1 + temp2;
temp1 = temp2;
temp2 = result;
}
return result;
}
}
TC, SC
- time complexity : O(n)
- space complexity : O(1)