프로그래머스 - 모음사전(Java)

dfs 문제입니다.

 

A, E, I, O, U 만을 사용하여 5자리 이내의 문자를 만들고, 정렬하여 주어지는 문자가 몇 번째인지 반환해야 합니다.

첫 번째 단어는 "A"이고, 두 번째 단어는 "AA"이며, 마지막 단어는 "UUUUU"입니다.

이 순서는 dfs(깊이 우선 탐색)을 통해 만들어지는 문자와 순서가 같습니다.

즉, dfs를 사용하여 문자를 만들고 만들어진 순서를 반환하면 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    
    final char[] WORDS = {'A', 'E', 'I', 'O', 'U'};
    final int MAX_LENGTH = 5;
        
    public int solution(String word) {
        int answer = 0;
        
        List<String> elements = new ArrayList<>();
        
        for(int i=0; i<WORDS.length; i++){
            dfs(elements, String.valueOf(WORDS[i]));
        }    
        
        for(int i=0; i<elements.size(); i++){
            if(elements.get(i).equals(word)){
                answer = i + 1;
                break;
            }
        }
        
        return answer;
    }
    
    void dfs(List<String> elements, String str){
        if(str.length() > MAX_LENGTH) return;
        
        if(!elements.contains(str)) elements.add(str);
    
        for(int i=0; i<WORDS.length; i++){
            dfs(elements, str+WORDS[i]);
        }
    }
}