프로그래머스 2단계 : 모음사전 (Java 자바)

문제설명

 

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

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

 

 

 

제한사항

 

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

 

입출력 예

 

 

풀이

 

알파벳 모음 'A', 'E', 'I', 'O', 'U'로 만들 수 있는 길이가 5 이하인 모든 단어가 사전에 수록되어 있을 때, 주어진 단어가 사전에서 몇 번째 단어인지를 찾는 문제입니다. 깊이 우선 탐색 (DFS)을 사용하여 문제를 풀었습니다.

 

1.. 'A', 'E', 'I', 'O', 'U'를 문자열 배열 'dict'에 저장합니다.

2. 깊이 우선 탐색 (DFS)을 시작하며, 현재 문자열 'cur'을 초기화하고, 주어진 단어 'word'를 찾을 때까지 탐색합니다.

3. DFS 함수 내부에서 현재 문자열 'cur'의 길이가 5에 도달하거나, 'cur'이 'word'와 동일한 경우를 처리합니다.

4. 주어진 단어 'word'를 찾았을 때, 순서를 'answer'에 저장합니다.

5. 'A', 'E', 'I', 'O', 'U'를 각각 현재 문자열 'cur'에 추가하며 DFS를 재귀적으로 호출합니다. 'cnt' 변수를 사용하여 단어의 순서를 증가시킵니다.

6. DFS 함수 호출이 끝나면, 주어진 단어 'word'의 위치를 찾아서 'answer'에 저장하고 반환합니다.

 

class Solution {
    public String[] dict;
    public int cnt = 0, answer = 0;
    
    public int solution(String word) {
        // 알파벳 모음 'A', 'E', 'I', 'O', 'U'를 배열에 저장합니다.
        dict = "AEIOU".split("");
        
        // 깊이 우선 탐색을 시작합니다.
        dfs("", word);
        
        return answer; // 결과를 반환합니다.
    }
    
    public void dfs(String cur, String word) {
        // 현재 문자열 'cur'이 길이 5에 도달하거나, 주어진 단어 'word'와 동일한 경우 처리합니다.
        if (cur.length() == 5 || cur.equals(word)) {
            if (cur.equals(word)) {
                answer = cnt; // 주어진 단어를 찾으면 그 때의 순서를 'answer'에 저장합니다.
            }
            return;
        }
        
        // 'A', 'E', 'I', 'O', 'U' 각각을 현재 문자열 'cur'에 추가하며 탐색을 진행합니다.
        for (int i = 0; i < 5; i++) {
            cnt++; // 단어 순서를 1 증가시킵니다.
            dfs(cur + dict[i], word); // 현재 문자열에 알파벳을 추가하며 다음 단계로 넘어갑니다.
        }
    }
}