링크

문제링크

문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

해결

9번째("AAAAU")에서 10번째("AAAE") 단어로 넘어갈때 'U'는 지워지고 그 전 자리인 4번째 'A'가 'E'로 바뀐것을 볼 수 있다.
이를 트리로 그려서 보면 DFS 알고리즘으로 트리를 탐색할 때와 같다.

단어의 규칙은
1.word의 길이가 5미만 일 경우는 'A'를 채워준다.
2.word의 길이가 5일 경우 마지막 알파벳을 다음 문자로 올려주지만 'U'일 경우 연속된 'U'를 모두 지워 준다.
이런 식으로 "UUUUU"까지 반복한다.

규칙을 파악하고나서 단순한 생각으로만 코드로 짜서 코드가 너무 길고 지저분해졌다.
DFS로 구현할 수 있다는것을 깨닫고 다시 DFS를 사용하여 코드를 짜보았다.

코드

class Solution {
    public int solution(String word) {
        int answer = 0;
        
        char[] alphabets = {'A', 'E', 'I', 'O', 'U'};
        int alphabetsIdx = 0;

        StringBuilder stringBuilder = new StringBuilder();


        while (!stringBuilder.toString().equals("UUUUU")) {
            //길이가 5보다 작을경우 A 추가
            if (stringBuilder.length() < 5) {
                stringBuilder.append(alphabets[alphabetsIdx]);
            } else {
                char lastCh = stringBuilder.charAt(stringBuilder.length() - 1);
                //제일 마지막이 'U'일때
                if (lastCh == 'U') {
                    int uidx = 0;

                    //'U'가 끝에서부터 연속적으로 어디까지 이어져 있는지 체크
                    for (int j = stringBuilder.length() - 1; j >= 0; j--) {
                        if (stringBuilder.charAt(j) == 'U') uidx = j;
                        else break;
                    }

                    //젤끝부분에 이어져있는 'U' 삭제
                    stringBuilder.delete(uidx, stringBuilder.length());
                    lastCh = stringBuilder.charAt(stringBuilder.length() - 1);
                    appendNextAlphabet(alphabets, lastCh, stringBuilder);
                } else {
                    appendNextAlphabet(alphabets, lastCh, stringBuilder);
                }
            }
            answer++;
            if (stringBuilder.toString().equals(word)) break;
        }
        
        return answer;
    }
    
    private static void appendNextAlphabet(char[] alphabets, char lastCh, StringBuilder stringBuilder) {
        char nextch = 0;

        for (int j = 0; j < alphabets.length; j++) {
            if (lastCh == alphabets[j]) {
                nextch = alphabets[j + 1];
            }
        }

        stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
        stringBuilder.append(nextch);
    }
}

DFS 를 사용한 풀이

class Solution {
        
    static int count = 0;

    public int solution(String word) {
        int answer = 0;
        
        char[] alphabets = {'A', 'E', 'I', 'O', 'U'};
        answer = dfs(alphabets, "", word);
        
        return answer;
    }
    
    public static int dfs(char[] alphabets, String word, String targetWord) {

        if (word.equals(targetWord)) return count;
        if (word.length() > 5) return 0;

        int totalCount = 0;
        count++;

        for (int i = 0; i < alphabets.length; i++) {
            totalCount += dfs(alphabets, word + alphabets[i], targetWord);
        }

        return totalCount;
    }
}