[프로그래머스] 모음사전, java

- 문제

프로그래머스

- 풀이

import java.util.*;

class Solution {
    
    //전역적으로 사용하기 위한 변수들을 static으로 선언시켜 주었습니다.
    static String[] str;
    static HashMap<String, Integer> key;
    static int idx;
    
    public int solution(String word) {
        
        //알파벳 모음을 순서대로 str에 담아줍니다.
        str = new String[]{"A","E","I","O","U"};
        
        //word라는 String을 key로 가지고, 
        //바로 해당 key의 순서를 바로 반환할 수 있는 HashMap을 만들어주었습니다.
        key = new HashMap<>();
        
        //현재 알파벳의 순서를 표현할 idx 변수입니다.
        idx = 1;
        
        //String을 이용하여 word의 표현을 진행하면
        //메모리를 많이 사용하게 되므로 StringBuilder를 사용해 보았습니다.
        StringBuilder sb = new StringBuilder();
        
        //dfs(깊이우선탐색)을 이용해 모든 word를 만들어봅니다.
        dfs(sb, 0);
        
        //dfs로 만들어진 사전 key에서 word를 이용해 바로 순서를 찾아 반환해줍니다.
        return key.get(word);
    }
    
    //문제의 핵심이되는 dfs함수입니다.
    //단어를 담을 StringBuilder와 현재 단어의 크기를 담을 size를 매개변수로 가집니다.
    static void dfs(StringBuilder sb, int size){
        
        //크기가 5을 넘어가면 dfs 탐색을 멈춥니다.
        if(size<5){
            
            //알파벳 모음을 순서대로 하나씩 대입하면서 탐색을 진행합니다.
            for(int i=0; i<5; i++){
                
                sb.append(str[i]);  //현재의 단어에 알파벳을 추가해줍니다.
                
                key.put(sb.toString(), idx++);  //이렇게 만들어진 단어를 사전에 추가하고, 사전의 순서를 증가시켜줍니다.
                dfs(sb, size+1);    //다음 단어를 만들기 위해 dfs를 진입해줍니다.
                
                sb.deleteCharAt(sb.length()-1);  //dfs를 겪고 나와서는 현재의 알파벳은 탐색이 끝났으므로 다시 제거해줍니다.
            }    
        }
    }
}