leetcode - count vowels permutation(java)

level - hard

[문제 내용]
n 길이의 아래 규칙을 만족하는 문자열의 개수

• 문자열은 'a', 'e', 'i', 'o', 'u' 로 이루어짐
• 'a' 다음에는 'e'가 와야한다.
• 'e' 다음에는 'a' 또는 'i'가 와야한다.
• 'i' 뒤에는 'i'가 오지 않는다.
• 'o' 뒤에는 'i' 또는 'u'가 와야한다.
• 'u' 뒤에는 'a'가 와야한다.
• 개수가 너무 많을경우 modulo 10^9+7

[example 1]

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

[example 2]

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

[example 3]

Input: n = 5
Output: 68

[해결 방법]
해당 문제는 dp를 이용해서 해결하였다.

먼저 해당 규칙을 다시 분석해 보면

• 'e', 'i', 'u' 뒤에는 'a'가 온다.
• 'a', 'i' 뒤에는 'e'가 온다.
• 'e', 'o' 뒤에는 'i'가 온다.
• 'i' 뒤에는 'o'가 온다.
• 'i', 'o' 뒤에는 'u'가 온다.

와 같고, 이 규칙을 활용하면 됩니다.

dp는 double[n][5]의 크기로 생성하고
dp[0] 은 아래와 같이 설정합니다.

a	e	i	o	u
1	1	1	1	1

다음 dp 값은 다시 분석한 규칙에 맞게 더한 값을 설정해줍니다.

'a' 로 끝나는 경우에 해당하는 'e', 'i', 'u'의 값을 더해서 넣어줍니다.

a	e	i	o	u
1	1	1	1	1
3

'e'로 끝나는 경우에 해당하는 'a', 'i'의 값을 더해서 넣어줍니다.

a	e	i	o	u
1	1	1	1	1
3	2

'i'로 끝나는 경우에 해당하는 'e', 'o'의 값을 더해서 넣어줍니다.

a	e	i	o	u
1	1	1	1	1
3	2	2

'o'로 끝나는 경우에 해당하는 'i'의 값을 넣어줍니다.

a	e	i	o	u
1	1	1	1	1
3	2	2	1

'u'로 끝나는 경우에 해당하는 'i', 'o'의 값을 더해서 넣어줍니다.

a	e	i	o	u
1	1	1	1	1
3	2	2	1	2

이런식으로 n-1 번 반복하여 n번째에 길이가 n인 문자열의 개수를 알아낼 수 있습니다.
위의 방법을 코드로 작성하면 아래와 같습니다.

class Solution {
    public int countVowelPermutation(int n) {
        double[][] dp = new double[n][5];
        for(int i=0; i<5; i++) {
            dp[0][i] = 1;
        }

        for(int i=1; i<n; i++) {
            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4];
            dp[i][1] = dp[i-1][0] + dp[i-1][2];
            dp[i][2] = dp[i-1][1] + dp[i-1][3];
            dp[i][3] = dp[i-1][2];
            dp[i][4] = dp[i-1][2] + dp[i-1][3];
            for(int j=0; j<5; j++) {
                dp[i][j] %= 1000000007;
            }
        }

        int answer = 0;
        for(int i=0; i<5; i++) {
            answer += dp[n-1][i];
            answer %= 1000000007;
        }

        return answer;
    }
}

dp는 항상..어렵다..