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

문제 링크

 프로그래머스

1. 문제 설명

머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 “aya”, “ye”, “woo”, “ma” 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

2. 접근법

“aya”,”ye”,”woo”,”ma” 로 조합할 수 있는 모든 단어를 찾는다는 것은 불가능하기도 하고 비효율적이라고 생각해서 다른 방법으로 접근했다.

접근한 방법은 “yewooma” 라는 문자열이 주어진다면, 새로운 문자열 A에다 “yewooma”의 앞단어부터 하나씩 넣어준다.

그리고 A가 ”aya”,”ye”,”woo”,”ma”가 될 때, A를 string.Empty 시켜준다.

“yewooma” 문자열의 끝까지 탐색을 마쳤을 때 문자열 A가 Empty라면, “yewooma”는 “aya”,”ye”,”woo”,”ma” 로 구성된 단어임을 알 수 있다.

오답인 경우도 봐보자.

예를 들어, “yewoomaa” 라는 문자열이 주어진다면,
“ye”,”woo”와 “ma” 까지는 문자열 A가 계속 Empty 상태가 되겠지만, 마지막 “a”는 A에 남게 된다.
그러므로, 탐색 종료 후 A가 Empty가 아니게 됨으로 “aya”,”ye”,”woo”,”ma”로 구성된 단어가 아님을 알 수 있다.

3. 제한 사항

제한 사항 중에 가장 중요한 내용은 아래의 내용이라 생각한다.

babbling의 각 문자열에서 “aya”, “ye”, “woo”, “ma”는 각각 최대 한 번씩만 등장합니다.즉, 각 문자열의 가능한 모든 부분 문자열 중에서 “aya”, “ye”, “woo”, “ma”가 한 번씩만 등장합니다.

“aya”,”ye”,”woo”,”ma”가 문자열에서 “한 번씩” 등장하기 때문에

STL의 std::map를 사용해 사용된 단어(Key)의 Value를 false에서 true로 바꾸어 한 번씩 사용되도록 하였다.

4. 코드

#include <iostream>
#include <vector>
#include <map>
#include <functional>

using namespace std;

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

    map<string, bool> canWords
    {
        {"aya",false},
        {"ye",false},
        {"woo",false},
        {"ma",false}
    };

    function<void()> initMap = [&canWords]
    {
        canWords["aya"] = false;
        canWords["ye"] = false;
        canWords["woo"] = false;
        canWords["ma"] = false;
    };
    
    string word;

    for (string babb : babbling)
    {
        initMap();

        word = "";

        for (auto b : babb)
        {
            word += b;

            if (canWords.find(word) != canWords.end())
            {
                canWords[word] = true;
                word = "";
            }
        }

        if (word.empty())
            answer += 1;
    }

    return answer;
}