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

1. 문제

모음사전

2. 개요

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

단어 하나가 매개변수로 주어질 때 이 단어가 사전의 몇 번째 단어인지를 리턴하는 문제.

3. 풀이 및 코드

3-1. 풀이

백트래킹을 이용한다. 해당하는 단어를 찾아낼 때 까지는 cnt를 늘려나가고, 단어를 찾은 이후로는 cnt를 늘리지 않는다.

백트래킹을 이용하면 길이가 5가 아닌 단어에 대한 처리를 따로 해 주어야 하는데, 빈 공간만큼 다른 기타 문자를 할당하여 이를 처리할 수 있도록 한다.

3-2. C#

using System;
using System.Collections.Generic;

public class Solution {
    static int[] vowelcnt = { 5, 5, 5, 5, 5, 5 };
    static int cnt = 0;
    static bool isFind = false;
    
    public int solution(string word) {
            Dictionary<string, int> dict = new Dictionary<string, int>() { { "A", 1 }, { "E", 2 }, { "I", 3 }, { "O", 4 }, { "U", 5 } };
            string target = "";

            foreach (char v in word)
                target += dict[v.ToString()].ToString();

            target = (target + "00000").Substring(0, 5);

            BT(target);

            return cnt;
        }

        void BT(string word, string made = "", int idx = 0)
        {
            if (idx == 5)
            {
                if (word == made)
                    isFind = true;

                if (!isFind)
                {
                    cnt++;
                    return;
                }

                else
                {
                    return;
                }
            }

            else
            {
                for (int i = 0; i < 6; i++)
                {
                    if (vowelcnt[i] > 0)
                    {
                        if (i == 0)
                            BT(word, (made + "00000").Substring(0, 5), 5);

                        else
                        {
                            vowelcnt[i]--;
                            BT(word, made + i.ToString(), idx + 1);
                            vowelcnt[i]++;
                        }
                    }
                }
            }
        }
}