[프로그래머스] 모음사전 - JAVA

문제

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

프로그래머스

 

코드

class Solution {
    static String arr [] = {"A", "E", "I", "O", "U"};
    static int count = 0;
    static String str = "";
    static int answer = 0;
    
    public int solution(String word) {
        back(word, 0);
        return answer;
    }
    
    public void back(String word, int depth){
        if(str.equals(word)){
            System.out.println(str);
            answer = count;
            return;
        }
        if(depth == 5){
            return;
        }
        
        for(int i=0;i<5;i++){
            count = count+1;
            str = str + arr[i];
            back(word, depth+1);
            str = str.substring(0, str.length()-1);
        }
    }
}

 

풀이

전형적인 백트레킹 문제

다만 종료조건을 작성하는 것이 어려웠다.

종료조건은 두 개로 설정한다.

1. 백트레킹을 통해 만들어진 문자열이 word하고 같을때

이 경우는 원하는 word를 만들었다는 뜻으로 count 값은 answer에 넣어준다.

2. 만들어진 문자열의 길이가 5일때

만들어진 문자열의 길이를 depth로 나타냈다.

문자열의 최대 길이는 5가 된다. 

따라서 문자열의 길이가 5일때 종료되도록 만들어준다.