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

옹알이 (1)

문제 링크

옹알이 (1)

분석

조카는 정해진 네 가지 발음을 할 수 있습니다.
"aya", "ye", "woo", "ma" 이 네 단어를 최대 한 번씩 사용해 조합한 발음밖에 하지 못합니다.

주어진 문자열 리스트 babbling에서 발음 가능한 문자열의 개수를 구해 반환해야합니다.

각 문자열의 가능한 모든 부분 문자열 중 "aya", "ye", "woo", "ma"는 한 번씩만 등장합니다.

문자열은 모두 소문자로 이루어져 있습니다.

풀이

#include <string>
#include <vector>

using namespace std;

// 발음 가능한 단어 목록
vector<string> str = { "aya", "ye", "woo", "ma" };

// 특정 문자열이 발음 가능한 조합인지 검증하는 함수
bool isValidWord(string babble)
{
    // 마지막에 발음한 단어를 저장해 중복 방지
    string lastword;
    
    // 문자열의 앞에서부터 순차적으로 검사
    for (int i = 0; i < babble.size(); ++i)
    {
        // 유효한 단어가 매칭됐는지 여부를 저장
        bool isMatch = false;
        
        // 발음 가능한 단어 목록을 순회하면서 검사
        for (int j = 0; j < str.size(); ++j)
        {
            string word = str[j];

            // 현재 위치에서 단어가 매칭되고, 이전 단어와 같지 않을 경우
            if (babble.substr(i, word.size()) == str[j] && lastword != word)
            {
                
                i += word.size() - 1;   // 현재 단어 길이만큼 인덱스를 점프
                lastword = word;        // 마지막 발음한 단어 갱신
                isMatch = true;         // 매칭 성공 여부 저장
                break;                  // 더 이상 현재 위치에서 다른 단어를 확인할 필요가 없다.
            }
        }
        
        // 4개의 단어 중 어느 것도 매칭되지 않으면 유효하지 않은 문자열
        if (!isMatch)
        {
            return false;
        }
    }
    
    return true;
}

int solution(vector<string> babbling) {
    int answer = 0;
    
    // 입력된 각 문자열 순회
    for (int i = 0; i < babbling.size(); ++i)
    {
        // 유효한 발음 조합인지 검사
        if (isValidWord(babbling[i]))
        {
            ++answer;
        }
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(n \times l)$입니다.

• babbling을 순회하는 반복문 $O(n)$
• 각 옹알이를 발음할 수 있는지 확인하는 반복문 $O(l)$
  • l은 현재 단어의 길이
• $O(n \times l)$

공간 복잡도는 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.02ms, 4.2MB)
테스트 2 〉 통과 (0.03ms, 4.21MB)
테스트 3 〉 통과 (0.02ms, 4.02MB)
테스트 4 〉 통과 (0.03ms, 4.21MB)
테스트 5 〉 통과 (0.02ms, 4.21MB)
테스트 6 〉 통과 (0.02ms, 4.18MB)
테스트 7 〉 통과 (0.02ms, 3.68MB)
테스트 8 〉 통과 (0.04ms, 4.17MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.02ms, 4.21MB)
테스트 11 〉 통과 (0.02ms, 3.64MB)
테스트 12 〉 통과 (0.01ms, 4.16MB)
테스트 13 〉 통과 (0.01ms, 4.07MB)
테스트 14 〉 통과 (0.02ms, 3.68MB)
테스트 15 〉 통과 (0.02ms, 4.22MB)
테스트 16 〉 통과 (0.02ms, 4.16MB)
테스트 17 〉 통과 (0.01ms, 3.68MB)