[프로그래머스/C++]Lv.2 - 모음사전

문제 링크

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

내 풀이

경우의 수 규칙이 있을거같았는데 생각하기 복잡해서 문제의 카테고리인 완전탐색으로 풀었다.
dfs 재귀를 만들어서 풀었다.
일단 정답을 찾은경우 재귀를 빨리 끝내기 위해 count == answer일 경우 return을 해두었다.
재귀 안에 for문으로 글자를 더한 후 카운트 증가 후 word가 검출되면 answer를 count로 갱신하고 return 한다.
start의 길이가 5일때 까지 재귀한다. 돌아오면 넣었던 마지막 글자를 뺴고 for문으로 인해 다음 글자를 넣고 다시 재귀한다.

내 코드

#include <string>
#include <vector>

using namespace std;

string AEIOU = "AEIOU";
int count = 0;
int answer = -1;

void dfs(string start, string word)
{
    if(count == answer)
        return;
    
    for(int i = 0; i < 5; i++)
    {
        start += AEIOU[i];
        count++;
        if(start == word)
        {
            answer = count;
            return;
        }
        if(start.length() < 5)
            dfs(start, word);
        start.pop_back();
    }
}

int solution(string word) {
    
    dfs("", word);
    
    return answer;
}

다른 사람의 풀이

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

using namespace std;

int solution(string word) {
    int answer = 0;
    map<char, int> alp;
    int next_word[5] = { 781, 156, 31, 6, 1 };
    
    alp.insert({'A', 0});
    alp.insert({'E', 1});
    alp.insert({'I', 2});
    alp.insert({'O', 3});
    alp.insert({'U', 4});
    
    int i = 0;
    for (const auto& w : word) {
        answer += 1 + alp[w] * next_word[i];
        i++;
    }
    
    return answer;
}

다른 사람의 풀이 해석

https://ggjjdiary.tistory.com/68
대부분은 완전탐색으로 했고 규칙을 찾은 답안을 가져왔다.