모음사전

문제

풀이

import java.util.*;

class Solution {
    static String[] str = {"A","E","I","O","U"};
    static int answer = 0; 
    static int cnt=0;
    
    public static void DFS(String tmp,String word){
        if(tmp.equals(word)){
            answer = cnt;
            return;
        }
        if(tmp.length() == 5){
            return;
        } 
        
        for(int i=0; i<5; i++){
            cnt++;
            DFS(tmp+str[i], word);
        }
    }
    
    public int solution(String word) {
        // A , E , I , O , U
        DFS("",word);
        return answer;
    }
}

기본적인 완전탐색의 템플릿 형태를 띈다. 빽트래킹을 설정해주고 for문을 돌려준다.
단 , tmp.equals(word) 형태의 빽트래킹이 최우선이 되어야한다. 왜냐하면 tmp.length() == 5 일 경우 빽트래킹을 해버리면 정답을 지나쳐버릴 수도 있기때문이다.
이런 문제를 항상 풀다보면 거의 빽트래킹 설정하는 부분에서 잘못된 부분이 발생한다.
이런 유형의 문제를 만나면 그러한 부분들을 신경쓰자.