문제

나의 요약

A, E, I, O, U 다섯 글자를 이용해 길이가 최대 5인 단어를 만들 수 있다. 이 단어들만 들어있는 사전이 있다고 해보자. 단어 word가 주어질 때 이것이 사전에서 몇 번째 단어인지 찾아내자.

접근 방식

처음에는 word의 글자를 인덱스 순서별로 조사해 규칙성이 있는 수식을 찾아내려했다. 하지만 규칙성을 알아내는데 어려움이 있어서, 그냥 사전 단어를 처음부터 탐색하자는 생각으로 완전 탐색을 하기로 했다.
5개의 글자로 길이가 5인 단어를 만드니, 대략 5^5 = 3125번의 탐색을 진행하면 된다. (물론 길이가 5 미만인 단어들도 있으니 정확히 저 값은 아니다.)

풀이

#include <string>
#include <vector>

using namespace std;

int answer = 0;
bool isFound = false;
string wordComponents[] = {"", "A", "E", "I", "O", "U"};

void Find(int index, string comp, string target)
{
    comp += wordComponents[index];
    bool strCompleted = index == 0 || comp.length() == 5;
    
    if(strCompleted)
    {
        if(!isFound)
        {
            answer++;
        }
    }
    else
    {
        for(int i = 0; i < 6; i++)
        {
            Find(i, comp, target);
            if(isFound) { return; }
        }
    }
    
    if(comp.compare(target) == 0)
    {
        isFound = true;
    }
}

int solution(string word) {
    
    for(int i = 1; i < 6; i++)
    {
        Find(i, "", word);
    }
    return answer;
}

Find 함수는 비교하는 string 변수 comp를 재귀적으로 변형해가는 함수이다. 마치 DFS를 진행하듯 순서가 먼저인 글자들부터 차례대로 comp에 들어가고, 원본 단어인 target과 비교하며 탐색을 진행한다.
comp와 target이 같다면 더이상 answer의 값을 증가시키지 않고 마무리하게 된다.

헤맨 지점

처음에는 재귀적으로 하는 것보다, 어차피 길이가 5인데 그냥 5중 for문 쓰는게 코드칠 때 빠르지 않을까? 했는데, comp를 늘렸다 줄였다 하는 과정이 for문으로 하면 너무 머리가 아파져 포기했다.

다시 돌아와야 한다는 포인트를 놓친 것이다. 이렇게 다시 돌아와야하는데, 탐색하는 숫자가 많지는 않을 때는 바로 재귀기법을 이용하자.