[프로그래머스][C++] 옹알이 (2)
옹알이 (2)
문제 링크
분석
babbling배열에서 발음할 수 있는 단어의 개수를 세는 문제입니다.
발음 할 수 있는 단어는 "aya", "ye", "woo", "ma"로 4가지 입니다.
연속으로 같은 발음을 할 수 없습니다.
babbling배열의 문자열을 앞에서부터 접근하며, 발음 가능한 단어로만 이루어져있는지 확인해야합니다.
풀이
babbling의 단어에서 한 글자씩 비교하는 방법입니다.
#include <string>
#include <vector>
using namespace std;
int solution(vector<string> babbling) {
int answer = 0;
// 발음 가능한 단어 목록
vector<string> babyWords { "aya", "ye", "woo", "ma" };
for (int i = 0; i < babbling.size(); ++i)
{
string substr; // babbling[i]에 있는 글자를 하나씩 추가한 부분 문자열
string prev; // 가장 최근에 발음한 단어
for (int j = 0; j < babbling[i].size(); ++j)
{
// babbling[i][j]의 1글자를 추가
substr += babbling[i][j];
for (int k = 0; k < babyWords.size(); ++k)
{
// 탐색 중인 부분 문자열이 발음할 수 있는 단어인 경우
if (substr == babyWords[k] && substr != prev)
{
prev = substr;
substr = "";
}
}
}
// 모든 문자가 올바르게 발음 가능한 단어 조합인 경우
if (substr == "")
{
++answer;
}
}
return answer;
}
babbling을 순회하면서, 각 단어(babbling[i])가 발음할 수 있는 조합으로만 이루어져있는지 확인합니다.
substr는 발음할 수 있는 단어인지 확인하는 용도입니다.
prev는 같은 단어가 연속으로 나오는지 확인하는 용도입니다.
babbling[i]를 순회할 때 substr에 글자를 하나씩 추가하고, 발음할 수 있는 단어인지 확인합니다.
발음할 수 있는 단어라면 가장 최근에 발음한 단어(prev)에 값을 갱신하고, substr을 비워줍니다.
만약 발음할 수 없는 단어라면 글자는 계속 추가되고, 결국 유효하지 않은 단어가 됩니다.
babbling[i]의 순회가 끝난 후 substr의 값이 비어있다면, 조카가 발음할 수 있는 단어 조합입니다.
비어있다면 발음할 수 있으므로 개수를 1개 증가합니다.
조카가 발음할 수 있는 단어를 기준으로 한 단어씩 비교하는 방법입니다.
#include <string>
#include <vector>
using namespace std;
// 발음 가능한 단어 목록
vector<string> babyWords { "aya", "ye", "woo", "ma" };
// 주어진 단어가 조카가 발음할 수 있는 단어 조합으로만 이루어져 있는지 검사하는 함수
bool canPronounce(string& babbling)
{
bool found = true; // 탐색 중인 부분 문자열이 발음 가능한 단어인지 여부
string prev; // 가장 최근에 발음한 단어
int j = 0; // 문자열을 탐색하는 인덱스
while (j < babbling.length())
{
for (int k = 0; k < babyWords.size(); ++k)
{
// j부터 babyWords[k]의 길이만큼 잘라낸 부분 문자열
string substr = babbling.substr(j, babyWords[k].length());
// 같은 단어가 연속으로 나오는지 확인
if (substr == prev)
{
return false;
}
// 탐색 중인 부분 문자열이 발음할 수 있는 단어인 경우
if (substr == babyWords[k])
{
found = true;
prev = substr;
j += babyWords[k].length();
break;
}
// 현재 탐색에서 발음 할 수 없는 단어인 경우
else
{
found = false;
}
}
// 발음 할 수 없는 단어인 경우
if (!found)
{
return false;
}
}
// 모든 문자가 올바르게 발음 가능한 단어 조합인 경우
return found;
}
int solution(vector<string> babbling) {
int answer = 0;
for (int i = 0; i < babbling.size(); ++i)
{
if (canPronounce(babbling[i]))
{
++answer;
}
}
return answer;
}
solution함수는 babbling을 순회하며, 각 단어(babbling[i])가 발음할 수 있는 조합으로만 이루어져있는지 확인합니다.
babyWords는 canPronounce함수에서 사용하기 위해 전역 변수로 존재합니다.
babyWords를 순회하며, babbling[i]의 j에서부터 babyWords[k]길이만큼 잘라 substr에 저장한 후 비교합니다.
만약 발음할 수 있는 단어라면 가장 최근에 발음한 단어(prev)에 값을 갱신하고, j를 단어 길이만큼 증가시킵니다.
그리고 발음할 수 있는 단어를 찾았으면 더이상 확인할 필요가 없으므로, 반복문을 탈출해 babbling[i]의 다음 구간을 확인합니다.
만약 발음할 수 없는 단어가 있다면 더 이상 검사하지 않고, 값이 반환됩니다.
성능 요약
babbling의 단어에서 한 글자씩 비교하는 방법의 성능입니다.
시간 복잡도는 $O(nm)$입니다.
babbling을 순회하는 반복문 $O(n)$babbling[i]를 순회하는 반복문 $O(m)$babyWords를 순회하는 반복문 $O(4) \approx O(1)$- $O(n) \times O(m) \times O(1)$
공간 복잡도는 $O(n)$입니다.
babyWords는 발음할 수 있는 단어 4개만 저장 $O(4) \approx O(1)$substr는babbling[i]의 글자에 비례해 저장하므로 $O(n)$- $O(1) \times O(n)$
테스트 1 〉 통과 (0.01ms, 3.63MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 3.66MB)
테스트 8 〉 통과 (0.01ms, 3.64MB)
테스트 9 〉 통과 (0.01ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 3.59MB)
테스트 11 〉 통과 (0.01ms, 4.11MB)
테스트 12 〉 통과 (0.03ms, 4.2MB)
테스트 13 〉 통과 (0.04ms, 4.21MB)
테스트 14 〉 통과 (0.02ms, 4.13MB)
테스트 15 〉 통과 (0.03ms, 4.42MB)
테스트 16 〉 통과 (0.04ms, 4.14MB)
테스트 17 〉 통과 (0.03ms, 4.27MB)
테스트 18 〉 통과 (0.02ms, 4.2MB)
테스트 19 〉 통과 (0.01ms, 4.13MB)
테스트 20 〉 통과 (0.02ms, 4.12MB)
시간 복잡도는 $O(nm)$입니다.
babbling을 순회하는 반복문 $O(n)$babbling[i]를babyWords로 문자열을 잘라 순회하는 반복문 $O(m \times 4) \approx O(m)$- $O(n) \times O(m)$
공간 복잡도는 $O(1)$입니다.
babyWords는 발음할 수 있는 단어 4개만 저장 $O(4) \approx O(1)$substr와prev는babyWords의 글자를 저장하므로 $O(1)$- $O(1) \times O(1)$
테스트 1 〉 통과 (0.01ms, 4.16MB)
테스트 2 〉 통과 (0.01ms, 4.16MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 3.64MB)
테스트 5 〉 통과 (0.01ms, 4.13MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.13MB)
테스트 8 〉 통과 (0.01ms, 4.14MB)
테스트 9 〉 통과 (0.01ms, 4.17MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.02ms, 4.2MB)
테스트 13 〉 통과 (0.04ms, 4.2MB)
테스트 14 〉 통과 (0.03ms, 4.21MB)
테스트 15 〉 통과 (0.02ms, 4.2MB)
테스트 16 〉 통과 (0.02ms, 4.13MB)
테스트 17 〉 통과 (0.03ms, 4.2MB)
테스트 18 〉 통과 (0.02ms, 4.14MB)
테스트 19 〉 통과 (0.01ms, 4.2MB)
테스트 20 〉 통과 (0.01ms, 4.2MB)
댓글남기기