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

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

프로그래머스

풀이

babbling 벡터에 단어가 들어올 때, "aya", "ye", "woo", "ma" 를 조합해서 단어를 만들 수 있는지 판단하는 문제입니다. 단, 한 단어를 연속으로 말 할 수는 없습니다.

 

단어가 하나씩 들어올 때 마다 판단하는 코드를 짜기에는 너무 복잡해 보여서, 4가지 단어를 사용해서 만들 수 있는 길이 30 이하의 모든 단어를 만들기로 했습니다.

 

모든 단어를 만들었다면, 단어가 들어올 때 해쉬에 존재하는지만 검사하면 답을 찾을 수 있습니다.

 

registString 재귀 함수를 사용해서 가능한 모든 단어를 만들어 줍니다. 이때, prev 변수를 사용해서 이전에 사용한 단어를 연속으로 사용하지 않도록 막아줍니다.

 

재귀를 사용했기 때문에 시간은 상당히 오래 걸립니다.

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

using namespace std;

vector<string> v({"aya", "ye", "woo", "ma"});
unordered_map<string, int> hash;

void registString(string str, string prev) 
{
    if (str.size() > 0 && str.size() <= 30) {
        ::hash[str] = 1;
       
        if (prev != "aya")
            registString(str+"aya", "aya");
        if (prev != "ye")
            registString(str+"ye", "ye");
        if (prev != "woo")
            registString(str+"woo", "woo");
        if (prev != "ma")
            registString(str+"ma", "ma");
    }
}

int solution(vector<string> babbling) {
    int answer = 0;
    
    registString("aya", "aya");
    registString("ye", "ye");
    registString("woo", "woo");
    registString("ma", "ma");
    
    for (auto i : babbling) {
        if (::hash[i]) answer++;
    }
    return answer;
}

다른 풀이

다른 분이 구현한 효율적인 풀이는 다음과 같습니다.

 

한 단어를 temp1에 문자 하나씩 추가하면서 옹알이 단어와 일치하면 temp1을 초기화 해줍니다. 이 때, 같은 단어가 연속으로 나왔는지 판단하기 위해 temp2 변수를 사용해 이전 옹알이 단어를 저장해둡니다. 

 

모든 문자를 검사하고 난 후 temp1이 비어있다면 한번도 break 되지 않은 것이므로 답에 추가합니다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<string> babbling) {
    int answer = 0;

    for(int i;i<babbling.size();i++)
    {
        string temp1="";
        string temp2="";
        for(char c:babbling[i])
        {
            temp1+=c;
            if(temp1 == "aya"||temp1 == "ye"||temp1 == "woo"||temp1 == "ma")
            {
                if(temp2 == temp1) break;
                temp2=temp1;
                temp1="";
            }
        }
        if(temp1.size()==0) answer++;
    }
    return answer;
}