[프로그래머스][JAVA][Lv. 2] 모음사전

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

class Solution {
    String[] strArr = new String[] { "A", "E", "I", "O", "U" };
    String answer;
    int count = 0;
    
    public int solution(String word) {
        answer = word;
        for (int i = 0; i < 5; i++) if(doDfs("", strArr[i])) return count;
        
        return -1;
    }
    
    private boolean doDfs(String result, String addStr) {
        StringBuilder tempWord = new StringBuilder().append(result).append(addStr);
        String tempToStr = tempWord.toString();
        
        count++;
        if (tempToStr.equals(answer)) return true;
        
        for (int i = 0; i < 5; i++) {
            if (tempToStr.length() < 5)
                if (doDfs(tempToStr, strArr[i])) return true;
        }
        
        return false;
    }
}

---

후기

생각이 잘 안 나서 며칠 고생했다. 그런데 나중에 생각해보니 그냥 일반적인 DFS였는데 왜 안 떠올랐는지 모르겠다...

재귀 호출 동안에 답을 찾으면 탈출을 시켜줄 수 있어야 효율적이다.

다른 사람 풀이에 인덱스를 이용한 풀이가 있던데 나중에 다시 살펴봐야겠다.