[Programmers] Lv2. 모음 사전 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

백트래킹(Backtracking)을 이용해 사전 순서대로 단어를 조합하는 방식으로 풀었습니다. 1)알파벳을 하나씩 붙이고 떼는 과정에서 인덱스 번호를 증가시키고, 2)원하는 단어를 찾으면 탐색을 중지하도록 구현하였습니다.

재귀(Recursion)와 백트래킹(Backtracking) 개념이 처음에는 익숙하지 않아, 코드로 구현하기 어려웠는데 점점 연습하다 보니 익숙해 지는 것 같습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
using namespace std;
const int VOWEL_NUM = 5;
const char vowel[VOWEL_NUM] = { 'A', 'E', 'I', 'O', 'U' };
bool isFindingWord = false;

void CreateCombinationWords(const string& word, string targetWord, int& index)
{
    if (targetWord.length() == VOWEL_NUM)
        return;

    for (int i = 0; i < VOWEL_NUM; i++)
    {
        targetWord.push_back(vowel[i]);
        index++;
        if (targetWord.compare(word) == 0)
        {
            isFindingWord = true;
            break;
        }

        CreateCombinationWords(word, targetWord, index);
        if (isFindingWord)
            break;

        targetWord.pop_back();
    }
}

int GetWordIndex(const string& word)
{
    int index = 0;
    string targetWord = "";
    CreateCombinationWords(word, targetWord, index);
    return index;
}

int solution(string word) {
    return GetWordIndex(word);
}

 

제출 결과