[프로그래머스] 완전탐색 - 모음사전 / 중복순열

문제

 

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<string> al = {"A", "E", "I", "O", "U"};
int count = 0;
int answer;

void dfs(string s, string word){

    if(s == word){
        answer = count;
        return;
    }
    
    if(s.size() == 5){
        return;
    }
    
    for(int i=0; i<al.size(); i++){
        count++;
        string str = s + al[i];
        dfs(str, word);
        
    }
}

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

모든 경우의 수를 구하며 탐색해야 하기 때문에 dfs(너비 우선 탐색)를 사용했고,

문자의 순서에 따라 다른 데이터로 인식하기 때문에 순열을 사용했다. 

중복을 허용해야 했기 때문에 탐색여부를 저장하는 visited는 사용하지 않았다.

 

모든 경우의 수를 구하면서 word와 같은 문자열이 만들어질 경우, dfs를 종료하고 해당 문자의 순서를 return 했다.

 

 

---

 

다른 사람 풀이

#include<bits/stdc++.h>
using namespace std;

int solution(string word) {
    int dp[6]={0,5};
    for(int i=2;i<=5;++i){
        dp[i]=5*(dp[i-1]+1);
    }
    string v="AEIOU";
    int ans=word.size();
    for(int i=0;i<word.size();++i){
        int p=v.find(word[i]);
        if(p)ans+=p*(1+dp[4-i]);
    }
    return ans;
}