프로그래머스 - 모음사전

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

---

문제 설명

"A", "E", "I", "O", "U" 5개 알파벳으로만 이루어진 길이 5 이하의 모든 단어가 적힌 사전이 있습니다.
사전의 첫  번째 단어는 "A"이고 그 다음은 "AA", 마지막 단어는 "UUUUU"입니다.

단어가 주어질 때 몇번째 단어인지 리턴하시오.

ex) "AAAAE" : 6, "I" : 1563

---

아이디어

완전탐색에 목록에 있는 문제로, 사전에 길이가 5*5*5*5*5 = 3125가지 밖에 안되기에 모든 조합을 미리 만들어두고 확인하는 것으로 해결할 수 있습니다. 보자마자 바로 완전탐색이라고 생각이 들도록 문제 크기를 잘 고려하는게 중요할 것 같습니다.

사전은 leaf까지 깊이가 5인 트리가 있다고 생각하고 A,E,I,O,U 순으로 재귀적으로 순회하며 번호를 체크하는 방식으로 구현했습니다. 어떻게 보면 이걸 그대로 트리로 잘 세팅하면 트라이랑 비슷한 형태인가 싶습니다.

---

코드

#include <bits/stdc++.h>

using namespace std;

map<string, int> dict;
int cnt = 0;

void MakeDict(vector<string> alphabets, string currentStr, int currentNum)
{
    if(currentNum == 5) return;
    
    for(auto alphabet : alphabets)
    {
        dict[currentStr + alphabet] = ++cnt;
        MakeDict(alphabets, currentStr + alphabet, currentNum + 1);
    }
}

int solution(string word) {
    vector<string> alphabets = {"A", "E", "I", "O", "U"};
    MakeDict(alphabets, "", 0);
    return dict[word];
}

메모리: 4.14 MB, 시간: 1.21 ms

---

 

다른분들의 풀이를 보는데 781에서 5의 제곱으로 나누어 구하는 방법은 진짜 어떻게 한건지 궁금합니다..