본문 바로가기
알고리즘/LeetCode

[Leetcode][Javascript][Easy] 70. Climbing Stairs

by Benjamin_Choi 2021. 5. 16.

https://leetcode.com/problems/climbing-stairs/

 

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

Example 1:

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

 

Example 2:

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

 

Constraints:

  • 1 <= n <= 45

첫 번째 풀이

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    return getSteps(n);
    
};

var getSteps = function(n) {
    if (n === 0) {
        return 1;
    } else if (n < 0) {
        return 0;
    } else {
        return getSteps(n-1) + getSteps(n-2);
    }
}

Recursion 을 써서 간단하게 해결해보려했는데 테스트 케이스 크기가 커지면서 시간 초과에 걸려서 실패했다. 메모이제이션을 적용해줘야겠다. 


두 번째 풀이 - 성공

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    return getSteps(n);
    
};

var getSteps = function(n) {
    if (memoize[n]) {
        return memoize[n];
    } else if (n === 0) {
        return 1;
    } else if (n < 0) {
        return 0;
    } else {
        if (memoize[n-1] && memoize[n-2]) {
            memoize[n] = memoize[n-1] + memoize[n-2];
            return memoize[n-1] + memoize[n-2];
        } else {
            return getSteps(n-1) + getSteps(n-2);    
        }
    }
}

var memoize = {
    2: 2,
    3: 3
};

메모이제이션을 적용해서 해결해줬는데, 문제의 예시로 나와줬던 n=2, n=3 일 때의 값을 memoize 객체에 넣어주고 시작해야 통과한다. 객체에 아무 것도 없이 시작하면 할당부터 안되서 똑같이 실패한다. n=2, n=3 을 적용해줬으므로 n=4 인 값을 확인할 때를 시작으로 해당되는 값을 memoize 객체에 넣어주게 된다. 그렇게 계속 상위의 값들까지 memoize 객체에 할당되면 재귀 함수의 깊이가 깊어질 필요 없이 점점 빨리 return 되므로 속도가 개선되어 통과할 수 있다.

댓글