[C++] 프로그래머스 모음 사전

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

풀이

완전 탐색을 통해 해결하는 문제입니다. for문과 dfs 를 사용해 문제를 해결할 수 있습니다.

 

for문 풀이의 경우 5중 루프를 사용합니다. 'AEIOU'를 저장하는 벡터 v를 만들고 순차적으로 단어를 만들면서 몇번째 위치하는지 unordered_map에 저장합니다. 이때, key는 현재 단어, value는 count 값입니다. 단어를 저장했다면 string의 pop_back() 함수를 사용해 가장 뒤의 단어를 빼줍니다.

모든 단어를 조합해 저장 후 답을 찾아내므로 dfs 풀이보다 느립니다.

 

dfs 의 경우 target 값을 찾으면 종료하므로 for문 풀이보다 빠르고, 코드도 간결합니다. 마찬가지로 모든 단어를 만들어가며 답을 찾아냅니다.

 

for 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<char> v{'A', 'E', 'I', 'O', 'U'};

int solution(string word) {
    int answer = 0;
    int n = v.size();
    int count = 0;
    unordered_map<string, int> um;
    string ss;
    
    for (int i=0; i<n; i++) {
        ss += v[i];
        count++;
        um[ss] = count;
        
        for (int ii=0; ii<n; ii++) {
            ss += v[ii];
            count++;
            um[ss] = count;
            
            for (int iii=0; iii<n; iii++) {
                ss += v[iii];
                count++;
                um[ss] = count;
                for (int iiii=0; iiii<n; iiii++) {
                    ss += v[iiii];
                    count++;
                    um[ss] = count;
                    for (int iiiii=0; iiiii<n; iiiii++) {
                        ss += v[iiiii];
                        count++;
                        um[ss] = count;
                        ss.pop_back();
                    }
                    ss.pop_back();
                }
                ss.pop_back();
            }
            ss.pop_back();
        }
        ss.pop_back();   
    }
    
    answer = um[word];
    return answer;
}

dfs 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<char> v{'A', 'E', 'I', 'O', 'U'};
int cnt = -1;
string target="";
int answer = 0;

void dfs(string w)
{
    cnt++;
    
    if (w == target) {
        answer = cnt;
        return;
    }
    
    if (w.size() >= 5) return;
    
    for (int i=0; i<5; i++) {
        dfs(w + v[i]);
    }    
}

int solution(string word) {
    target = word;     
    dfs("");

    return answer;
}