[84512] 모음 사전

✔ 모음 사전

[프로그래머스 84512]

문제 분석하기

DFS를 수행하며 가능한 모든 단어를 저장한 후 일치하는 단어의 인덱스를 찾아 반환

손으로 풀어보기

1. DFS를 수행하며 가능한 모든 단어를 HashMap에 저장
2. HashpMap에서 일치하는 단어의 인덱스를 찾아 반환

슈도코드 작성하기

word(단어)
words(알파벳 모음들)
index(단어 순서 인덱스) = 0
map(가능한 모든 단어들을 저장하는 hashMap)
dfs("", 0)
answer(사전에서의 단어 순번)
answer = map.get(word);
answer 반환

dfs {
    hashMap.put(단어, index)
    index 증가
    if (단어의 길이가 5라면) {
        return
    }
    for (i->5만큼) {
        dfs(현재 단어 + words[i], 현재 단어의 길이 + 1)
    }
}

코드 구현하기

/**
 * 84512) 모음_사전
 */
public class K007_84512 {
    // words(알파벳 모음들)
    static String[] words = { "A", "E", "I", "O", "U" };
    static Map<String, Integer> map;
    static int index;

    // word(단어)
    public int solution(String word) {
        // index(단어 순서 인덱스)
        index = 0;
        // map(가능한 모든 단어들을 저장하는 hashMap)
        map = new HashMap<>();
        // dfs("", 0)
        dfs("", 0);
        // answer(사전에서의 단어 순번)
        int answer = map.get(word);
        // answer 반환
        return answer;
    }

    // DFS를 수행하며 가능한 모든 단어 저장하기
    private void dfs(String str, int length) {
        // hashMap.put(단어, index)
        map.put(str, index);
        // index 증가
        index++;
        // 단어의 길이가 5라면
        if (length == 5) {
            return;
        }
        for (int i = 0; i < 5; i++) {
            // dfs(현재 단어 + words[i], 현재 단어의 길이 + 1)
            dfs(str + words[i], length + 1);
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K007_84512 solution = new K007_84512();

        String word = "AAAAE";
        int result = solution.solution(word);

        System.out.println(result);
    }
}