프로그래머스 모음사전

https://school.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

---

우선 총 5개의 문자가 돌아간다는 것에서 5진수를 생각해봤습니다.

그리고 직감적으로 생각해보면 왠지 자리수라는 것도 생각해 볼수 있는데

그럼 자리수의 정보가

54 , 53, 52, 51 , 50

로 표현되지 않을까 하는 발상에서 출발해봤습니다.

그런데 이러면 실제 문제와 맞지 않는데

한번 간단히 문제의 예시를 나열해보고, 몇개의 케이스를 추가해보았습니다.

A => 1 AA => 2 AAA => 3 AAAA => 4 AAAAA =>5 AAAAE => 6 AAAE => 10 AAE => 34

여기서 좀 조심히 관찰해보면

A는 자리 수에 관계없이 +1 의 정보만 리턴하고

E 는 어떤 자리 수 에 따라 특이한 정보값을 증가시키는데요.

AAAAE(6) 은 AAAAA(5) 보다 1 차이가 나고

AAAE(10) 은 AAAA(4) 보다 6 차이가 나고 AAAAA(5) 보다는 5 차이가 납니다.

AAE(34) 는 AAA(3) 보다 31 차이가 나고 AAAE(10) 보다는 25 차이가 납니다.

네 처음에 생각했던 54, 53, 52, 51, 50 의 패턴도 보이는데요

실제 같은 자리 수의 단어를 비교( AAAE, AAAA 간 비교 등) 에서는

다음과 같은 공식으로 동작합니다.

---

각 자리는 이전 자리들의 가중치 [ 54, 53, 52, 51, 50 ] 를 가짐.

따라서 AAE 에서 'E' 는 이전 자리수 52 + 51 + 50 = 31 의 가중치를 가지는데

E 는 [ 'A', 'E', 'I', 'O', 'U' ] 에서 두번째(인덱스로는 1) 을 이기 때문에

[ 31 * index + 1 ] 의 정보를 가진다.

---

여기서 +1 을 하는 이유는 단어의 누적, A가 항상 +1 정보를 누적하는 것에서 영감을 얻었습니다.

그래서 한번 테스트 코드에 있는 "I"(1563) 를 한번 공식으로 풀어보면,

(54 + 53 + 52 + 51 + 50 ) * 2 + 1 = ( 625 + 125 + 25 + 5 + 1 ) * 2 + 1 = 781 * 2 + 1 = 1563

으로 공식이 성립함을 알 수 있습니다!

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int getInfoNum(int idx) {
    int sum = 0;
    int count = 0;
    while (count <= 4 - idx) {
        sum += pow(5, count++);
    }
    return sum;
}

int solution(string word) {
    int answer = 0;
    vector<char> strArr = {'A', 'E', 'I', 'O', 'U'};
    vector<char> wordArr(word.begin(), word.end());

    for (int index = 0; index < wordArr.size(); ++index) {
        int num = find(strArr.begin(), strArr.end(), wordArr[index]) - strArr.begin();
        answer += getInfoNum(index) * num + 1;
    }

    return answer;
}