Leetcode Climbing Stairs Python 풀이

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Climbing Stairs
등급: Easy

내용: n의 계단을 1개 또는 2개씩 올라가는데의, 총 몇 가지 독특한 방법으로 n 계단을 올라갈 수 있는가?

stairs

<코드>

class Solution(object):
    def climbStairs(self, n):
        cache = {}
        
        def climbStairs_2(n):
            if n in cache:
                return cache[n]
            
            if n <= 3:
                result = n
            else:
                result = climbStairs_2(n-1) + climbStairs_2(n-2)
                
            cache[n] = result
            
            return result
        
        return climbStairs_2(n)

본다면 어제 올린 코드와 굉장히 비슷하다는 것을 알 수 있을 것이다.

 

오랜만에 10분안에 풀은 코드이다. (어제와 거의 똑같기 때문에..)

 

<논리>

Climbing Stairs는 Fibonacci Number, 피보나치 수와 별 다른 점이 없다. n=6까지 계산을 해보니까, n=6은 n=5와 n=4의 결과들을 더한 값이었다.

 

그래서, 간단하게 위에처럼 코딩이 되었다. cache라는 hash table을 통해 값들을 저장하여 빠른 속도를 추구하였다. 그래서, n값이 cache이 있다면 바로 cache[n]이 나오게 if statement를 적어주고, base case로 n<=3일때는 n을 그대로 반환하게 하였다. 만약 n>3이라면, fibonacci number처럼 재귀 호출을 통해 그 전 숫자들을 계산하게 하였다

 

그 후, result을 그저 반환하면 끝!

<오류, 힘들었던 점>

오랜만에 없음

<총평 외 comment>

오랜만에 쉽고 편했다.

 

Happy coding!

Climbing Stairs - LeetCode