99클럽 코테 스터디 13일차 TIL [LeetCode] Count Sorted Vowel Strings (Java)

문제

[LeetCode] Count Sorted Vowel Strings

풀이

모음을 사전순으로 정수 n 길이의 문자로 조합하는 문제

• vowels 배열에 모음을, 조합한 문자열 결과를 result에 저장한다.
• 각 위치의 인덱스를 indices에 저장한다.
• while (true) 반복문을 통해 모든 조합을 생성한다.
• StringBuilder를 사용하여 현재 인덱스 배열에 따라 문자열을 조합하고 결과 리스트에 추가한다.
• 인덱스 배열을 업데이트해 다음 조합을 생성한다.
  • 각 위치의 인덱스를 순회하여 가능한 모든 조합을 생성
  • 가장 오른쪽 위치부터 시작하여 최대 인덱스(4)를 초과한 경우 왼쪽으로 이동하여 인덱스를 증가, 그 오른쪽은 모두 동일한 값으로 설정

정답 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countVowelStrings(int n) {
        char[] vowels = {'a', 'e', 'i', 'o', 'u'};
        List<String> result = new ArrayList<>();
        int[] indices = new int[n];

        while (true) {
            StringBuilder sb = new StringBuilder();
            for (int index : indices) {
                sb.append(vowels[index]);
            }
            result.add(sb.toString());

            int pos = n - 1;
            while (pos >= 0 && indices[pos] == 4) {
                pos--;
            }

            if (pos < 0) {
                break;
            }

            indices[pos]++;
            for (int i = pos + 1; i < n; i++) {
                indices[i] = indices[pos];
            }
        }

        return result.size();
    }
}

개선점

메모리와 시간 복잡도가 높아 비효율적이다.
문자열을 직접 생성하지 않고 풀 수 있는 문제다.

다른 풀이

다이나믹 프로그래밍(DP) 활용

class Solution {
    public int countVowelStrings(int n) {
        int[][] dp = new int[n + 1][6];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 5; j++) {
                if (i == 1) {
                    dp[i][j] = j;
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[n][5];
    }
}

조합 활용

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