1641-kir3i.md

1641. Count Sorted Vowel Strings

Solution

• 시간복잡도: O(N)

• 알고리즘

  수학, 구현

• 풀이설명

  문제에서 구하는 결과는 결국 중복조합을 계산해야합니다. 따라서 이 문제는 중복조합을 구현하는 것이 관건입니다. Python의 경우 큰 정수를 기본적으로 지원하기에 팩토리얼만 구현하면 되지만 C++의 경우 자료형에 신경써야 합니다. 30!만 되어도 long long의 범위를 한참 넘는데 문제에선 n이 최대 50이므로 팩토리얼을 한 번에 구하기 보단 곱하고 나누는 과정을 반복하는 게 좋습니다.

• 소스코드

  • C++

    class Solution {
    public:
        int countVowelStrings(int n) {
            return nHr(5, n);
        }
        
        int nHr(int n, int r) {
            double ans = 1.;
            for(int i=0; i<r; i++)
                ans *= 1.0 * (n+r-1-i) / (i+1);
            return round(ans);
        }
    };

  • Python

    class Solution:
        f = {}
        def countVowelStrings(self, n):
            return self.nHr(5, n)
    
        def nHr(self, n, r):
            return self.fact(n+r-1) // self.fact(n-1) // self.fact(r)
    
        def fact(self, n):
            if n <= 1:
                return 1
            elif n not in self.f:
                self.f[n] = n * self.fact(n-1)
            return self.f[n]