[프로그래머스] 모음사전 C++

 

1. 문제

 

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

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

 

2. 코드

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

using namespace std;

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }
    
    sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

 

3. 해설

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }

재귀 함수를 통해서 모든 경우의 수를 저장합니다.

경우의 수는 1자리일 때, 2자리일 때, 3자리일 때, 4자리일 때, 5자리일 때 모든 경우의 수를 구해야합니다.

따라서 1자리의 경우

for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
}

이 부분이 aeiou[0] ~aeiou[4] 까지의 값이 한번씩 호출 되면서 끝납니다.

2자리의 경우 위의 for문이 aeiou[0]+aeiou[0]~aeiou[4] 에서부터 aeiou[4]+aeiou[0]~aeiou[4] 까지 계산함으로 총 25가지의 문자열이 저장됩니다.

이와 같은 방법으로 5자리의 경우까지 재귀함수를 통해 저장합니다. 

sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

그 후, 사전적 배열로 나열해줘야합니다.

기존에 저장된 배열은 A,E,I,O,U,AA,AE,AI,AO,AU.... 등의 순서로 구성되어 있습니다.(함수 호출 순서에 따라 달라질 수 있으나 (1자리수...2자리수...3자리수.... 로 저장)

기본적으로 sort 함수는 string 변수에서 사전적 순서로 정렬해주기 때문에 별도의 판별 함수를 넣지 않아도 됩니다.

그 후 for문을 통해 받은 word 값과 nums[i]의 값이 같다면 해당 번호를 뽑아냅니다.

벡터는 0번부터 시작하기에 +1을 해주면 몇번째 수인지를 도출할 수 있습니다.

※ for문을 쓰지 않고 find() 함수를 통해서 한줄로 해결할 수도 있습니다.