개요

모음사전

• 문제 설명
  사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

  단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
  

접근 방식

1. DFS방식을 사용했다.
   빈 string형 변수 word를 함수에 넘기고, 문제에서 준 순서에 맞게 moum배열에 들어있는 char형 모음들을 'A'부터 word에 더해가며
   answer값을 증가하는 식으로 재귀를 시행한다.
2. 각 재귀단계에서 완성이 되었다면 true를 리턴해서 그다음 스텝으로 가지 않고 바로 탈출하도록 구현하였다.

   bool ret = dfs(target,moum,answer, tmp);
   if(ret)
   	return true;

전체 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool dfs(string target, const char moum[], int& answer, string word) {
    if (word == target)
            return true;
    if(word.length()==5)
        return false;;
    for (int i = 0; i < 5; i++) {
        string tmp = word+moum[i];
        answer++;
        bool ret = dfs(target,moum,answer, tmp);
        if(ret)
            return true;
    }
    return false;
}

int solution(string word) {
    int answer = 0;
    char moum[] = { 'A', 'E', 'I', 'O', 'U' };
    dfs(word, moum, answer, "");
    return answer;
}

문풀후생

무난하게 DFS방식으로 푼 문제였다.