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

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

프로그래머스

 

중복순열을 연습하기 좋은 문제다. 

 

중복순열은 AAAAA AAAAB ... 등으로 이뤄지기 때문에 순열이나 조합을 선택했을 때 처럼 방문체크를 할 필요가 없다. 이정도 난이도는 코딩테스트 1~2번으로 충분히 나올 수 있다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 0;
string alpha = "AEIOU";
bool flag = false;
void dfs(string str, string target){
    if(flag) return;
    
    if(str == target){
        flag = true;
        return;
    }
    answer++;

    if(str.size() == 5) return;
    
    for(int i = 0; i < 5; i++){
        str.push_back(alpha[i]);
        dfs(str, target);
        str.pop_back();
    }
}

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