문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/84512

문제 설명

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

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

제한 사항

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

입출력 예

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

정답 해설

           ""
     /  |  |  |  \
   "A" "E" "I" "O" "U"
   /|\  /|\  /|\  /|\  /|\
"AA" ... "AE" ... "AI" ... "AU"

해당 문제를 트리 모양으로 나타내면 그 일부는 위와 같다. 누가 봐도 DFS(깊이우선탐색)를 통한 완전 탐색문제임을 확인할 수 있다.

class Solution {
    static int count = -1; // -1부터 시작하는 이유는 => 아무것도 없는 공백을 탐색 시작 단어로 생각하고 시작하기 위함
    static String[] alphabets = {"A", "E", "I", "O", "U"}; // 5개의 모음
    static boolean flag = false; // 목표 단어를 찾았는지 여부

    public int solution(String word) {

        String myWord = ""; // 현재 찾은 단어
        dfs(word, myWord); 
        return count; // 몇번째 단어인지 반환

    }

    private void dfs(String word, String myWord) {

        // 목표 단어를 찾았다면 더이상 탐색하지 않고 재귀 함수들 차례로 종료, 찾지 못했다면 count 증가시키고 계속 탐색
        if (!flag) { 
            count++;
        }

        if (myWord.equals(word)) { // 목표 단어를 찾았다면 flag를 true로 변경
            flag = true; 
            return;
        }

        if (myWord.length() == 5 || flag) { // 단어의 길이가 5이거나 목표 단어를 찾았다면 탐색 종료
            return;
        }

        for (String alphabet : alphabets) {
            dfs(word, myWord + alphabet); // 단어 길이가 5가 되면 그 이전으로 돌아가 모음을 하나씩 추가하면서 재귀 호출
        
        }
//        dfs(word, myWord + "A");
//        dfs(word, myWord + "E");
//        dfs(word, myWord + "I");
//        dfs(word, myWord + "O");
//        dfs(word, myWord + "U");
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String word = "AAAAE";
        sol.solution(word);
    }
}