Leet Code - 70. Climbing Stairs(C++)

예제: Climbing Stairs

문제
You are climbing a stair case. It takes n steps to reach to the top.

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

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 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

풀이

Input을 1과 2의 조합을 통해 만들 수 있는 경우의 수를 구하는 문제이다.

처음에는 재귀함수를 사용한 동적 프로그래밍으로 아래와 같이 풀었다.

class Solution {
public:
	int climbStairs(int n) {
		vector<int> cache(n + 1, 0);

		return solve(cache, n);
	}

	int solve(vector<int>& cache, int n) {
		if (n <= 1) return 1;

		if (cache[n] != 0) return cache[n];

		return cache[n] = (solve(cache, n - 1) + solve(cache, n - 2));
	}
};

1과 2만 사용한다면 피보나치와 같은 문제이기 때문에, 아래와 같이 간단하게 풀어도 된다.

class Solution {
public:
	int climbStairs(int n) {
		vector<int> cache(n + 1);
		cache[0] = 1;
		cache[1] = 1;

		for (int i = 2; i <= n; i++) {
			cache[i] = cache[i - 1] + cache[i - 2];
		}

		return cache[n];
	}
};

그런데, 속도가 자꾸만 안나오는 것이 아닌가?
다른 풀이를 참고해보았는데, 풀이가 매우 비슷한데 속도차이가 나오는 것이 있다.

바로, vector 대신 unordered_map을 사용한 것이다.
검색을 해 보니, unordered_map의 경우 vector와 같은 기존의 컨테이너보다 메모리를 더 사용한다는 단점이 있지만(벤치마크에서는 2배 정도 더 사용), 접근속도가 비약적으로 상승한다고 한다. 따라서, 요소가 정렬되어 저장될 필요가 없고, 접근이 잦은 경우 unordered_map을 사용하면 매우 유리하다고 한다.

따라서, 위 두 번째 풀이에서 vector를 unordered_map으로 바꾸기만 해 주면 속도가 매우 빨라진다.

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	unordered_map<int, int> map;

	int climbStairs(int n) {
		map[0] = 1;
		map[1] = 1;

		for (int i = 2; i <= n; i++) {
			map[i] = map[i - 1] + map[i - 2];
		}

		return map[n];
	}
};

풀이 후기

역시 STL을 잘 알아야 속도까지 챙기며 알고리즘을 풀 수 있다. 이렇게 하나씩 배우며 머리에 새겨두자!