[프로그래머스] 2단계 - 모음 사전

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U' 만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 수록되어 있을 때, 주어지는 단어가 사전에서 몇 번째 단어인지 return

 

문제 풀이법

재귀를 통해서 문제를 풀 수 있다

"AAAAE"는 6번째 단어인데 이유는 "A" -> "AA" -> "AAA" -> "AAAA" -> "AAAAA" -> "AAAAE" 이기 때문이다

문자열 뒤에 계속해서 글자를 붙여주며, 재귀를 돌면 해당 사전을 만들 수 있다

 

재귀의 탈출 조건은 글자 길이가 5 이상이거나, target 문자열과 현재 문자열이 같을 때이다

target 문자열과 현재 문자열이 같으면 answer을 저장해야한다

 

탈출 조건에 부합하지 않으면 몇 번째 단어인지 cnt + 1 해주고 for문을 돈다

for문에서는 char ch[5] = { 'A', 'E', 'I', 'O', 'U' }를 돌면서 현재 문자열 뒤에 문자를 붙여주면서 재귀를 타면 된다 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

char ch[5] = {'A', 'E', 'I', 'O', 'U'};
int answer = 0;
int cnt = 0;

void dfs(string str, string target) {
    if (str.compare(target) == 0) {
        answer = cnt;
        return ;
    }
    
    cnt++;
    
    if (str.size() >= 5)
        return ;
    
    for (int i = 0; i < 5; i++) {
        dfs(str + ch[i], target);
    }
}

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