[프로그래머스] Level 2. 모음사전

https://school.programmers.co.kr/questions/80728

프로그래머스

 

 

사전순으로찾다가, 내가 원하는 글자가 나오면 멈춘다. 문제는 사전순서대로  어떻게찾냐인듯.

dfs를 이용해서 푼다. dfs 의 반환형이 void 가 아니라 boolean인 이유는, 원하는 단어를 찾았는지 안찾았는지를 판별하기 위함이다. 

 

탐색순서는 다음처럼 진행된다

 

A [] [] [] []
A A [] [] []
A A A [] []
A A A A []
A A A A A
A A A A E
A A A A I
A A A A O
A A A A U
A A A E []
A A A E A
...

 

#include <string>
#include <vector>

using namespace std;

string vowel ="AEIOU";
string word;
int answer = 0;
bool dfs(int idx, string str){
    if(idx == 5) return false;
    
    for(auto ch: vowel){
        answer++;
        if(str+ch == word) return true;
        if(dfs(idx+1,str+ch))return true;
    }
    return false;
}
int solution(string word) {
    ::word = word;
    dfs(0,"");
    return answer;
}