99클럽 코테 스터디 7일차 TIL DFS(모음사전)

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

프로그래머스

 

문제를 읽으면서 든 생각은 순열, 조합, 부분집합, DFS 어쨌든 재귀로 풀어야겠다고 생각했다

문자열을 재귀에 담아 만들면서 돌리고, 원하는 문자가 나왔을 때 그때까지의 번호를 return 하는 형식.

총 길이가 5이므로, 5까지만 만들고 되돌리고를 반복하면 된다.

몇번째인지를 담는 변수는 함수에 넣으면 안됨!

문자가 5를 넘어가면 안되니 5에서 return 조건 걸고, 5가 되기 전에 주어진 단어가 나올 수 있으니 이때도 return 조건문을 걸어줬다.

 

구현하고 보니 뭔가 살짝 깔끔하지 않은 느낌이 드는 데 좀 더 고민해봐야겠다 

class Solution {
    
    static int ans;
    static int answer;
    static String[] arr = {"A", "E", "I", "O", "U"};
    
    public static void dfs(String now, int cnt, int start, String word){
        if(cnt == 5) {
            if(now.equals(word)){
            answer = ans;
            }
            return;
        }
        if(now.equals(word)){
            answer = ans;
            return;
        }
        for(int i=start; i<5; i++){
            ++ans;
            dfs(now+arr[i], cnt+1, start, word);
        }
    }
    
    public int solution(String word) {
        
        dfs("", 0, 0, word);
        
        return answer;
    }
}