[Javascript] 프로그래머스 - 모음사전

문제 설명

알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 사전에 정렬되어 있습니다. 예를 들어, 첫 번째 단어는 "A", 두 번째 단어는 "AA", 마지막 단어는 "UUUUU"입니다. 주어진 단어 word가 사전에서 몇 번째 단어인지 찾는 함수를 구현해야 합니다.

제한 사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

해결 방법

알고리즘: DFS(깊이 우선 탐색)

1. 사전에 나올 수 있는 단어를 DFS를 이용해 순차적으로 생성하면서 탐색합니다.
2. DFS를 수행하며 단어를 만들고, 카운트를 증가시킵니다.
3. 생성한 단어가 word와 일치하면 현재 카운트 값을 반환합니다.
4. 단어의 길이가 5가 되면 더 이상 탐색하지 않습니다.
5. DFS의 백트래킹을 활용하여 모든 가능한 단어를 순회하며 word의 위치를 찾습니다.

시간 복잡도

DFS를 사용하여 가능한 모든 단어를 탐색하며, 각 자리에서 N=5 개의 알파벳 중 하나를 선택합니다.
단어의 최대 길이가 M=5 이므로, 최악의 경우 모든 단어를 생성해야 하며, 이는 O(N^M) = O(5^5) = O(3125) 의 시간 복잡도를 가집니다.

구현 코드

function solution(word) {
    const chars = ["A", "E", "I", "O", "U"];
    let count = 0;
    
    function dfs(str) {
        if (str === word) return count;
        if (str.length === 5) return null;
        
        for (let i = 0; i < 5; i++) {
            count++;
            const result = dfs(str + chars[i]);
            if (result !== null) return result;
        }
        
        return null;
    }

    return dfs("");
}