[LeetCode] - 1641_Count Sorted Vowel Strings

문제 소개

• Medium / Dynamic Programming
• https://leetcode.com/problems/count-sorted-vowel-strings/description/

풀이

public int countVowelStrings(int n) {
    int[] dp = new int[]{1, 1, 1, 1, 1};

    while (--n > 0) {
        for (int i = 3; i >= 0; i--) { // 각 인덱스 a, e, i, o 에 대한 개수를 할당함
            dp[i] += dp[i + 1]; // a는 나머지 4개를 포함한 경우의 수, e는 나머지 3개를 포함한 경우의 수, i 는 나머지 2개, o는 나머지 1개, u는 제외 / u는 항상 1개 => 모두 u인경우
        }
    } // 이를 n이 1일 될 때까지 반복하여, 2자리 => 3자리 => 4자리 => ... 순으로 계산해 나간다.

    return Arrays.stream(dp).sum();
}

각 인덱스에 해당하는 모음인 `a, e, i, o, u` 에 해당하는 DP 배열을 만들어준다.

그 중 `u`를 제외한 `a, e, i, o` 에 대한 경우의 수를 구해나간다.

`u`를 제외하고 나머지 경우에 대해서만 계산하는 이유는 아래와 같은 조건 때문이다.

• 조합된 문자의 경우 사전순으로 정렬되어있다.

그렇기에 n이 2일 때, `ae` 혹은 `ea` 더라도 사전순으로 정렬된 결과 `ae` 가 되며, `u`의 경우는 `uu` 인 경우만 포함되는 것이다.

 

참고로 이번 문제의 풀이를 찾아보다가 시간 복잡도를 O(n)까지 줄인 케이스를 발견했다.

public int countVowelStrings(int n) {
    return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
}

코드도 무척이나 간단하며, 위에서 설명한 것과 같이 `a, e, i, o` 에 대한 경우의 수를 구한다.

여기서 24로 나누는 이유는 조합을 사용하기 때문이다.

조합식은 n개의 자리수가 주어졌을 때, 5개의 모음을 배치해야하므로 `C(n+4, 4)` 가 된다.

이는 중복 조합을 이용한 식으로 `C(n+r-1, r-1)`을 이용한 것으로 보인다.

 

이를 계산해보면 아래와 같은 식을 얻을 수 있다.

• (n+4)! / 4!(n+4-4)!
• (n+4)! / 4!n!
• (n+4)(n+3)(n+2)(n+1)(n) / 4!n!
• (n+4)(n+3)(n+2)(n+1) / 24