프로그래머스 - 모음사전

 코딩테스트 고득점 Kit 완전탐색 Level 2 모음사전 문제이다. 이 문제는 a,e,i,o,u 다섯 모음으로 이루어진 모음 사전에서 어떤 단어가 몇번째 단어인지 알아내는 문제이다. 완전 탐색, 백트래킹으로 모든 단어의 조합을 구하는 연산의 수는 5^5 = 3125밖에 되지 않고, 모든 단어 조합의 수 또한 5 + 25 + 125 + 625 + 3125 = 3905개밖에 안되기 때문에 전역 배열에 담기에도 충분한 크기이다. 

 

#include <string>
#include <vector>

using namespace std;

vector<string> words;
char alphabet[5] = {'A', 'E', 'I', 'O', 'U'};

void func(int index, string temp)
{
    if (index == 5)
    {
        return;
    }
    
    for (int i = 0; i < 5; i++)
    {
        words.push_back(temp + alphabet[i]);
        func(index + 1, temp + alphabet[i]);
    }
}

int solution(string word) {
    int answer = 0;
    string temp = "";
    
    func(0, temp);
    
    for (int i = 0; i < words.size(); i++)
    {
        if (word == words[i])
        {
            answer = i + 1;
            break;
        }
    }
    
    return answer;
}