옹알이1

 

나는 모든 옹알이의 순열을 생성했다.

그리고 순열에 중복 방지 처리를 하지 않아, 비효율적이다.

일단 통과는 했으나, 입력값의 크기가 컸다면 통과하지 못했을 것이다.

ex) aya aya aya aya aya aya 같은 게 6개.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_set>

using namespace std;

//4P1 ~ 4P4 순열

int solution(vector<string> babbling) {
    vector<string> ayaya = { "aya", "ye", "woo", "ma" };
    unordered_set<string> ayaSet;
    int answer = 0;

    sort(ayaya.begin(), ayaya.end());

    for (int r = 1; r <= 4; ++r) 
    {
        do
        {
            string str = "";
            for (int i=0; i<r; ++i)
            {
                str += ayaya[i];
            }
            ayaSet.insert(str);

        } while (next_permutation(ayaya.begin(), ayaya.end()));
    }

    for (const string& s : babbling)
    {
        if (ayaSet.find(s) != ayaSet.end())
            ++answer;
    }

    return answer;
}

 

순열의 중복 제거는 조합 생성처럼 생성할 r만큼 true한 배열을 이용한다.

 

그러나, 이 문제를 푸는 데에는 훨씬 효율적인 방법이 있었다.

옹알이와 같은 문자를 공백으로 변환하여 공백 또는 비어있는 원소를 카운트하면 되는 것이다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<string> babbling) {
    int answer = 0;
    vector<string> words = {"aya", "ye", "woo", "ma"};

    for (const string& s : babbling) {
        string temp = s;
        for (const string& word : words) {
            size_t pos;
            while ((pos = temp.find(word)) != string::npos) {
                temp.replace(pos, word.length(), " "); // 공백으로 치환하여 연속 발음 방지
            }
        }
        temp.erase(remove(temp.begin(), temp.end(), ' '), temp.end()); // 공백 제거
        if (temp.empty()) {
            answer++;
        }
    }

    return answer;
}

 

다른 분 코드

answer += s.find_first_not_of(' ') == string::npos;

공백이 아닌 원소의 첫번 째 문자 위치를 반환. = npos 없다면, true(1)

 

멋있다.

int solution(vector<string> babbling) {
    int answer = 0;
    for (const string& word : babbling) {
        string s = word;
        size_t pos;
        pos = s.find("aya");
        if (pos != string::npos) s.replace(pos, 3, " ");
        pos = s.find("ye");
        if (pos != string::npos) s.replace(pos, 2, " ");
        pos = s.find("woo");
        if (pos != string::npos) s.replace(pos, 3, " ");
        pos = s.find("ma");
        if (pos != string::npos) s.replace(pos, 2, " ");
        answer += s.find_first_not_of(' ') == string::npos;
    }
    return answer;
}