모음사전

[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/84512

문제 설명

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

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

제한사항

word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’로만 이루어져 있습니다.

입출력 예

word	result
“AAAAE”	6
“AAAE”	10
“I”	1563
“EIO”	1189

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”, “AAA”, “AAAA”, “AAAAA”, “AAAAE”, … 와 같습니다. “AAAAE”는 사전에서 6번째 단어입니다.

입출력 예 #2

“AAAE”는 “A”, “AA”, “AAA”, “AAAA”, “AAAAA”, “AAAAE”, “AAAAI”, “AAAAO”, “AAAAU”의 다음인 10번째 단어입니다.

입출력 예 #3

“I”는 1563번째 단어입니다.

입출력 예 #4

“EIO”는 1189번째 단어입니다.

로직

쉽게 for문으로만 풀수 있을 줄 알았지만, 무조건 시간 초과가 뜨게 되어있는 문제이다.

사전의 순서를 보면, A - AA - AAA - AAAA - AAAAA - AAAAE - AAAAI - AAAAO -AAAAU - AAAE - AAAEA … 순서로 진행된다.

맨 끝자리의 경우 index가 1씩 증가하게 되고,

4번째 자리의 경우에는 index가 6씩 증가하게 된다.(없는 경우 포함)

3번째 자리의 경우에는 index가 31씩 증가하게 된다. ((6*5) +1 )

2번째 자리의 경우에는 index가 156씩 증가한다. ((31* 5) +1)

1번째 자리의 경우에는 index가 781씩 증가하게 된다.((156 * 5)+1)

이러한 식을 통해 단어의 index에 빠르게 도달할 수 있다.

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Solution
{
    public static int solution(string word) {
        string str = "AEIOU";
        int[] inc = new int[] {781,156,31,6,1};
        int index,result=word.Length;
        for(int i =0;i<word.Length;i++)
        {
            index= str.IndexOf(word[i]);
            result += inc[i] * index;
        }
        return result;
    }


    public static void Main(string[] args)
    {
        string word = "AAAAE";
        Console.WriteLine(solution(word));
        
        
    }
}

모음사전 [프로그래머스](C#)