모음사전

문제 설명

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

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

풀이

public class VowelDictionarySearch
{
    private static Dictionary<char, int> _vowelIndex = new Dictionary<char, int>()
    {
        { 'A', 0 },
        { 'E', 1 },
        { 'I', 2 },
        { 'O', 3 },
        { 'U', 4 },
    };

    private static int _length;

    public static int Solution(string word)
    {
        _length =  word.Length;
        
        int index = 0;

        for (int i = 0; i < _length; i++)
            index += AddCalculatedIndexContribution(word[i], i);
        
        return index;
    }

    private static int AddCalculatedIndexContribution(char c, int index)
    {
        int contribution = 0;
        
        index = _length - index - 1;

        for (int i = index; i >= 0; i--)
        {
            contribution += (int)Math.Pow(5, i);
        }
        
        contribution *= _vowelStartIndex[c];

        contribution++;
        
        return contribution;
    }
}

접근 방법

A에서 E사이에 몇 개의 글자가 있을지 알아봄
a _ _ _ _

5 = 5
5 * 5 = 25
5 * 5 * 5 = 125
5 * 5 * 5 * 5 = 625
총 780개의 글자가 있어
e 자체는 781번째 글자임을 알게 됨
같은 방식으로 I는 1563번째 글자임
...

ae는 몇번째 글자일지 알아보려고 생각하니
aa와 ae사이에
aa _ _ _
5 = 5
5 * 5 = 25
5 * 5 * 5 = 125
총 130개의 글자가 있어 131번째 글자임을 알게 됨

해당 과정에서 각각의 글자에 대해서
((5^1 +5^2 + 5^3 ... 5^x) + 1) * 1 + 1
(여기서 x는 해당 글자가 몇번째 글자에 해당하는지에 따라 달라짐)
라는 식을 통해 해당 글자보다 앞에 있는 글자의 개수를 알아낼 수 있다는 것을 알게됨

함수 설명

    private static int AddCalculatedIndexContribution(char c, int index)
    {
        int contribution = 0;
        
        index = _length - index - 1;

        for (int i = index; i >= 0; i--)
        {
            contribution += (int)Math.Pow(5, i);
        }
        
        contribution *= _vowelIndex[c];

        contribution++;
        
        return contribution;
    }

• 해당 방식을 적용한 함수로, 해당 함수에 주어진 문자의 모든 글자를 각각 입력해 도출된 값을 더하면 사전에서 몇번째 단어인지 알 수 있음
• c는 문자에서 하나의 알파벳을 의미하며, index는 전체 글자에서 몇번째 인지를 의미

index = _length - index - 1;

• 문자의 전체 길이에서 해당 문자 뒤로 올 수 있는 빈칸의 개수를 의미하므로 전체 길이에서 해당 값을 빼고 하나를 더 뺀 값이 빈칸의 개수를 의미함

  "AAAAA"에서 'A'와 0을 입력
  → 전체 길이가 5이고 1번째 글자이므로 뒤에 올 수 있는 빈칸은 4개

• 빈칸으로 인해 만들어질 수 있는 글자 개수만큼을 더해 준 뒤에 해당 알파벳이 사전에서 몇번째 순서인지를 곱함

• 해당 과정을 모든 글자에 대해서 반복하면 전체에서의 순서를 알 수 있음