[c++ programmers 모음사전]

처음에는 경우의 수 구해서 좀 무식하게 풀었다.

#include <string>
#include <vector>

using namespace std;

int solution(string word) {
    int answer = 0;
   
    for (int i = 0; i < word.size(); ++i){
        if (word[i] == 'A'){
            answer += 1;
        }
        
        if (word[i] == 'E'){
            if (i == 0){
                answer += 781 + 1;
            }
            if (i == 1){
                answer += 156 + 1;
            }
            if (i == 2){
                answer += 31 + 1;
            }
            if (i == 3){
                answer += 6 + 1;
            }
            if (i == 4){
                answer += 2;
            }
        }
        
        if (word[i] == 'I'){
            if (i == 0){
                answer += 781 * 2 + 1;
            }
            if (i == 1){
                answer += 156 * 2 + 1;
            }
            if (i == 2){
                answer += 31 * 2 + 1;
            }
            if (i == 3){
                answer += 6 * 2 + 1;   
            }
            if (i == 4){
                answer += 3;
            }
        }
        
        if (word[i] == 'O'){
            if (i == 0){
                answer += 781 * 3 + 1;
            }
            if (i == 1){
                answer += 156 * 3 + 1;
            }
            if (i == 2){
                answer += 31 * 3 + 1;
            }
            if (i == 3){
                answer += 6 * 3 + 1;   
            }
            if (i == 4){
                answer += 4;
            }
        }
        
        if (word[i] == 'U'){
            if (i == 0){
                answer += 781 * 4 + 1;
            }
            if (i == 1){
                answer += 156 * 4 + 1;
            }
            if (i == 2){
                answer += 31 * 4 + 1;
            }
            if (i == 3){
                answer += 6 * 4 + 1;   
            }
            if (i == 4){
                answer += 5;
            }
        }
    }
    return answer;
}

하지만 이 방법은 자릿수가 늘어나면 쓸 수 없기 때문에

구글 검색으로 더 간단히 풀이를 찾아보았고, DFS로 푸는 방법이 있었다!!

(출처 : https://comdolidol-i.tistory.com/253)

왜 깊이 탐색을 생각 못했지...역시 답을 알고 나면 갑자기 쉽게 느껴진다. 

 

1. map을 이용하여 A E I O U로 이루어진 5자리 단어 사전을 만든다.

2. 입력 단어에 해당하는 순서를 찾는다.