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

완전탐색

A, E, I, O, U 으로만 이루어진 단어 사전이 있다. 이 사전에 수록된 단어의 최대 길이는 5일때,

특정 단어가 주어지면, 이 단어의 순서를 반환하는 문제

 

<사전 예시>

"A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"

 

접근방법

어차피 한번에 단어 한개만 주어져서 저장해두고 쓰는 것도 불필요해서, 그냥 매번 순서를 셌다..(이게맞나 암튼 완전탐색임)

DFS처럼 순서대로 단어를 체크했고, 이 문제에서는 의외로(?) 관건이 언제 재귀함수를 종료할 것인가 였다.

1. cnt 증가 (단어 순서)

2. 찾아야할 단어의 순서인지 확인 -> 맞으면 answer = cnt 담고 함수 종료

3. 단어의 길이가 5이면 함수 종료 (이래야 단어의 길이가 6인 것 까지 순서를 세지 않음)

4. 현 단어에 모음 순서대로 하나씩 붙이기 (dfs 호출)

 

오답노트

- 처음 dfs를 호출할 때 '현 단어(word)'에 빈 문자열을 보낼 거기 때문에 cnt는 그것까지 포함하고 있어서, 마지막에 answer 반환할 때 1빼줘야한다.

 

소스코드

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

using namespace std;

int cnt = 0;
int answer = 0;
char vowels[5] = {'A', 'E', 'I', 'O', 'U'};

void dfs(string word, string goal){
    cnt++;
    if(word == goal){
        answer = cnt;
        return;
    }
    if(word.size() == 5)
        return;
    
    for(int i = 0 ; i < 5 ; i++){
        dfs(word+vowels[i], goal);
    }
}

int solution(string word) {

    dfs("", word);
    
    return answer-1;
}