[LeetCode] 1220. Count Vowels Permutation

문제 출처: https://leetcode.com/problems/count-vowels-permutation/

Count Vowels Permutation - LeetCode

 

문제

정수 n이 주어질 때, 다음의 규칙에 따라서 얼마나 많은 n 길이의 문자열을 만들 수 있는지 계산해야 한다:

• 소문자 모음('a', 'e', 'i', 'o' , 'u')을 대상으로 한다.
• 모음 'a' 뒤에는 'e'만 따라올 수 있다.
• 모음 'e' 뒤에는 'a' 또는 'i'만 따라올 수 있다.
• 모음 'i' 뒤에는 'i'는 따라올 수 없다.
• 모음 'o' 뒤에는 'i' 또는 'u'만 따라올 수 있다.
• 모음 'u' 뒤에는 'a'만 따라올 수 있다.

 

답이 매우 클 수 있기 때문에 10^9 + 7로 나눈 나머지를 반환하라.

 

예제

Input: n = 1
Output: 5

Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Input: n = 2
Output: 10

Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Input: n = 5
Output: 68

 

풀이

다이내믹 프로그래밍(DP) 방식을 이용한 문제 접근

 

n이 1과 2일 때의 예를 생각해보자.

n = 1 → [a, e, i ,o, u]
n = 2 → [ae, ea, ei, ia, ie, io, iu, oi, ou, ua]

n = 2인 케이스의 문자열은 n = 1일 때의 문자들에 대해서, 각 문자열이 어떤 문자로 끝나는지에 따라 문제에서 주어진 규칙을 적용한 결과이다. 이를 확장하여, 길이가 n = k일 때의 문자열을 알기 위해서는 이전 n = k-1일 때의 문자들이 어떤 문자로 끝나는지를 알면 쉽게 계산이 가능하다.

 

추가적으로 문제에서 구하고자 하는 값이 문자열의 '수'라는 점을 고려할 때, 문자열을 기록하는 것이 아닌 각 모음으로 끝나는 문자열이 몇 개 있는지를 저장하는 방식으로 문제를 풀 수 있다.

 

이 내용을 기반으로 아래와 같은 점화식을 만들어 볼 수 있다.

- dp[i][vowel] : 길이가 i 인 문자열 중에서 vowel로 끝나는 문자열의 수

dp[i]['a'] = dp[i-1]['e'] + dp[i-1]['i'] + dp[i-1]['u']
dp[i]['e'] = dp[i-1]['a'] + dp[i-1]['i']
dp[i]['i'] = dp[i-1]['e'] + dp[i-1]['o']
dp[i]['o'] = dp[i-1]['i']
dp[i]['u'] = dp[i-1]['i'] + dp[i-1]['o']

이를 이용하여 다음과 같이 구현하였다.

var countVowelPermutation = function(n) {
    const charSet = ['a', 'e', 'i', 'o', 'u'];
    const module = 1000000007;

    let dp = new Map();
    for (let i = 0; i < charSet.length; i++) { dp.set(charSet[i], 1); }

    // 길이 n의 문자열의 수를 구하기 위한 반복문
    let k = 1;
    while (k < n) {
        const curStep = new Map();
        for (let i = 0; i < charSet.length; i++) { 
            switch (charSet[i]) {
                case 'a':
                    curStep.set('a', (dp.get('e') + dp.get('u') + dp.get('i')) % module);
                    break;
                case 'e':
                    curStep.set('e', (dp.get('a') + dp.get('i')) % module);
                    break;
                case 'i':
                    curStep.set('i', (dp.get('e') + dp.get('o')) % module);
                    break;
                case 'o':
                    curStep.set('o', (dp.get('i')) % module);
                    break;
                case 'u':
                    curStep.set('u', (dp.get('i') + dp.get('o')) % module);
                    break;
            }
        }
        dp = curStep;
        k += 1;
    }

    let ans = 0;
    for (let val of dp.values()) { ans += val; ans %= module; }
    return ans;
};

코드를 작성함에 있어서, DP를 적용하기 위한 자료구조로 맵 구조를 사용했다는 특징이 있으며 이외 다른 부분은 설명과 동일하다.

 

 

Github: 1220.js

opwe37/Algorithm-Study