[프로그래머스] 옹알이 (1) C++

27 Jan 2023 in Study on Coding Test

여러 방법이 있었겠지만 나는 백트래킹을 이용한 문제

정답제출코드

#include <string>
#include <vector>

using namespace std;

int answer_st = 0;
string bab[4] = {"aya", "ye", "woo", "ma"};

void backtrack(string s, string i)
{
    if (s.length() > 15)
        return;
    else if (s == i)
    {
        answer_st++;
        return;
    }
    
    for (int j = 0; j < 4; ++j)
    {
        string tmp = s + bab[j];
        backtrack(tmp, i);
    }
}

int solution(vector<string> babbling) {
    int answer = 0;
    int len = babbling.size();
    
    for (int i = 0; i < len; ++i)
    {
        string s = babbling[i];
        for (int j = 0; j < 4; ++j)
        {
            backtrack(bab[j], s);
        }
    }
    
    answer = answer_st;
    return answer;
}

문제 조건에서 babbling[i]의 길이가 15이하라는 점을 이용했다.

그래서 무작정 다 조합을 해보았다.

다 따지면서 맞는 경우가 나올 때 answer의 개수가 1 증가하도록 구현하였다.

백트래킹의 특성상 시간이 오래 걸리도록 결과가 나왔다..