프로그래머스 모음사전 (C++)

프로그래머스

알파벳 모음 A, E, I, O, U만을 이용해서 만들 수 있는 길이 5 이하의 모든 단어를 저장하고 있는 사전이 있습니다.

단어를 입력 받을 때, 해당 단어가 사전의 몇번째 위치에 저장되어 있는치 구해주세요.

(단어 저장 순서는 A, AA, AAA, AAAA ,AAAAA, AAAAE, AAAAI . . . . . )

 

 

풀이 방법

규칙을 찾아서 풀어줍니다.

AAAAA = 5
AAAAE = 6
AAAAI = 7 
AAAAO = 8 
AAAAU = 9

5번째 알파벳은 1씩 증가하는 규칙이 있습니다.

 

AAAA -> 4 
AAAE = 10
AAAI = 16 
AAAO = 22 
AAAU = 28

4번째 알파벳은 6씩 증가합니다.

 

AAA = 3 
AAE = 34
AAI = 65

3번째 알파벳은 31씩 증가하는 규칙이 있습니다.

 

즉, 4번째는 5번째의 증가 크기 * 5 + 1

3번째 알파벳은 4번째 알파벳의 증가 크기 * 5 + 1 

점화식을 구한다면 아래와 같습니다.

vector<int> p(5);
p[4] = 1; 
for (int i = 3; i >= 0; i--)
    p[i] = p[i+1] * 5 + 1;

이렇게 구한 알파벳 변화에 따른 순서의 증가폭을 이용하면 쉽게 풀이할 수 있습니다.

 

 

정답 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string word) {
    
    vector<int> p(6);
    for (int i = 4; i >= 0; i--)
        p[i] = p[i+1] * 5 + 1;
    
    // 증가폭에 곱해줄 크기
    map<char, int> idx = {{'A', 0}, {'E', 1}, {'I', 2}, {'O', 3}, {'U', 4}};
    
    //사이즈 만큼 초기화 (A일 경우 0을 곱해줘야 하기 때문에 미리 수를 더해줌)
    int answer = word.size();
    for (int i = 0; i < word.size(); i++)
        answer += p[i] * idx[word[i]];
    
    return answer;
}