[Programmers] 모음사전

문제

코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;
int cnt = 0;
void dfs(string s, string word){
    
    if(s == word){
        answer = cnt;
        return;
    }
    cnt++;
    if(s.size()<5) {
        dfs(s+"A", word);

    }
     
    char c = s.back();
    s.pop_back();
    switch(c){
        case 'A':
            dfs(s+"E", word);
            break;
        case 'E':
            dfs(s+"I", word);
            break;
        case 'I':
            dfs(s+"O", word);
            break;
        case 'O':
            dfs(s+"U", word);
            break;
        case 'U':
            break;
    }
}


int solution(string word) {
    
    dfs("", word);
    
    return answer;
}

풀이

풀고 보니 간단했지만, 좀 헤맸고 솔직히 좀 얻어걸렸다. 하다보니 돼버린 느낌.
재귀함수를 이용했을 때 어떤 순서로 단어가 만들어지는지를 생각하는 게 힘들었다.

모든 경우에서 다음번째 경우 1순위는 뒤에 A가 추가되는 것이므로, 처음에 size가 5보다 작다면 A를 추가하여 재귀함수를 호출한다.

또 각 재귀함수에서 맨 뒤에 있는 문자를 다음 순서의 문자로 변경하여 또 재귀함수를 호출한다.

디테일하게 다 생각해보려하면 머리가 복잡해지는데, 결국 재귀함수는 처음에 호출한 재귀를 타고 들어가면서 처리하기 때문에 이렇게 사전식 순서를 구성할 때 적합한 것 같다.