[프로그래머스] 모음사전 C++ 풀이 및 해설

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

프로그래머스

 

 

풀이 방법

A -> AA -> AAA -> AAAA

    -> AAAAA -> AAAAE -> AAAAI -> AAAAO -> AAAAU

    -> AAAE

    -> AAAEA -> AAAEE -> AAAEI -> AAAEO -> AAAEU

    -> ...

 

잘 생각해보면... DFS 방식이다.

[A, E, I, O, U] 배열을 생각해보자.

A를 먼저 넣고 한 깊이를 증가해 또 배열을 탐색한다.

그럼 또 A를 먼저 넣게된다.

그렇게 A A A A A를 계속 담고 길이가 5가되었다.

길이 4인 A A A A 에서 배열 A를 담았더니 길이 5인 AAAAA가 된 것이다.

그럼 다음은? A A A A에서 E를 담아야하니 AAAAE이다.

 

그러다 A A A A U까지 담았으면?

A A A E 에 A, E, I, O, U를 붙일 차례이다.

 

매 문자를 붙일때마다 카운트를 세어주고.

원하는 문자열일 만들어졌을때 현재 카운터가 답이다.

 

이 개념을 설명하기 뭐하다... 그냥 DFS 개념을 공부하면 이해가 될 문제이다!!

 

 

 

전체 코드

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

int cnt = 0;
void DFS(string word, string str, int *answer) {
    char c[5] = {'A', 'E', 'I', 'O', 'U'};
    
    if(word==str) {
        *answer=cnt;
        return;
    }

    
    for(int i=0; i<5; i++) {
        if(str.length()<5) {
            cnt++;
            DFS(word, str+c[i], answer);
        }
    }
    
}

int solution(string word) {
    int answer = 0;
    DFS(word, "", &answer);
    return answer;
}