[level 1] 옹알이 (2) - 133499

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

프로그래머스

---

설계

가능한 옹알이가 { "aya", "ye", "woo", "ma" } 이므로 직관적으로 'a', 'y', 'w', 'm' 으로 시작하지 않는 단어(babbling)은 로직을 피하고 가능한 옹알이가 나오면 그부분을 잘라 계속 비교하고 완벽히 다 잘라져서 문자열이 공백이 되면 answer의 카운트를 올린다.

 

구현

#include <string>
#include <vector>

using namespace std;


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

	for (int i = 0; i < babbling.size(); i++)
	{
		if (babbling[i][0] == 'a'
			|| babbling[i][0] == 'm'
			|| babbling[i][0] == 'w'
			|| babbling[i][0] == 'y')
		{
			
			string preWord = "";
			bool exitCount = true;
			while (exitCount)
			{

				exitCount = false;
				if (babbling[i] == "")
				{
					answer++;
					break;
				}

				if (preWord != word[0] && babbling[i].substr(0, word[0].size()) == word[0])	// aya
				{
					babbling[i] = babbling[i].substr(word[0].size(), babbling[i].size());
					preWord = word[0];
					exitCount = true;
				}

				if (preWord != word[1] && babbling[i].substr(0, word[1].size()) == word[1])	// ye
				{
					babbling[i] = babbling[i].substr(word[1].size(), babbling[i].size());
					preWord = word[1];
					exitCount = true;
				}

				if (preWord != word[2] && babbling[i].substr(0, word[2].size()) == word[2])	// woo
				{
					babbling[i] = babbling[i].substr(word[2].size(), babbling[i].size());
					preWord = word[2];
					exitCount = true;
				}

				if (preWord != word[3] && babbling[i].substr(0, word[3].size()) == word[3])	// ma
				{
					babbling[i] = babbling[i].substr(word[3].size(), babbling[i].size());
					preWord = word[3];
					exitCount = true;
				}
			}


		}

	
	}

	return answer;
}

 

 

리펙토링

#include <string>
#include <vector>

using namespace std;

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

    for (const string& b : babbling) {
        
        // [가지치기 (Early Exit)]
        // 빈 문자열이거나, 첫 글자가 a, y, w, m 중 어느 것도 아니라면 발음 불가능한 단어로 판정
        if (b.empty() || (b[0] != 'a' && b[0] != 'y' && b[0] != 'w' && b[0] != 'm')) {
            continue; // 아래의 복잡한 비교 로직을 무시하고, 즉시 다음 단어로 점프합니다. (속도 향상)
        }

        int idx = 0;           
        int prev_match = -1;   
        bool is_valid = true;  

        // 2. 현재 단어(b)의 끝에 도달할 때까지 반복 검사합니다.
        while (idx < b.length()) {
            bool matched = false; // 이번 턴에 4개 단어 중 하나라도 일치했는지 확인하는 플래그
			
            // 3. 4가지 발음 단어들을 차례대로 비교합니다.
            for (int j = 0; j < 4; j++) {
                
                // 조건 1: 연속된 발음이 아닐 것 (prev_match != j)
                // 조건 2: 현재 위치(idx)부터 words[j]의 길이만큼 잘라서 비교했을 때 일치할 것
                // b.compare(시작위치, 비교할길이, 비교할문자열) == 0 이면 완전히 일치한다는 뜻입니다.
                if (prev_match != j && b.compare(idx, words[j].length(), words[j]) == 0) {
                    idx += words[j].length(); // 일치한 단어의 길이만큼 인덱스를 앞으로 점프! (문자열 자르기 대체)
                    prev_match = j;           // 방금 일치한 단어의 번호를 기억 (연속 방지용)
                    matched = true;           // 일치하는 단어를 찾았다고 표시
                    break;                    // 단어를 찾았으므로 나머지 발음은 검사할 필요 없이 for문 탈출
                }
            }
			// 4. 4개 단어를 다 뒤져봤는데 일치하는 게 하나도 없다면?
            // -> 조카가 발음할 수 없는 이상한 문자열이 섞여 있다는 뜻입니다.
            if (!matched) {
                is_valid = false; 	// 불가능한 단어로 판정
                break;      		// 더 이상 검사할 필요 없으므로 while문 탈출      
            }
        }
		// 5. 문자열 끝까지 무사히 검사를 마쳤고(is_valid == true),
        // 남은 찌꺼기 문자 없이 인덱스가 문자열 길이와 딱 맞아떨어지면 정답 개수 증가
        if (is_valid && idx == b.length()) {
            answer++;
        }
    }

    return answer;
}

주요 리팩토링 포인트

1. substr() 사용 지양 (공간/시간 복잡도 최적화)

• 문제점: babbling[i] = babbling[i].substr(...) 코드는 문자열을 자를 때마다 새로운 문자열 객체를 메모리에 생성하고 복사합니다. 단어가 길어질수록, 자르는 횟수가 많아질수록 엄청난 메모리 낭비와 시간 지연(오버헤드)이 발생합니다.
• 해결책: 문자열을 직접 자르는 대신, **'현재 읽고 있는 위치(인덱스)'**만 숫자로 기억하면서 앞으로 이동하는 방식을 사용합니다. 이를 통해 문자열 복사 없이 원본 문자열을 한 번만 쭉 훑으면서 검사할 수 있습니다.

2. 반복되는 if문 병합 (가독성 향상)

• 문제점: "aya", "ye", "woo", "ma" 4개 단어에 대해 완전히 동일한 로직의 if문이 4번 반복되고 있습니다. 코드가 길어지고 오타가 발생하기 쉽습니다.
• 해결책: 4개의 발음을 배열(vector)에 넣어두고, 내부에서 for문을 돌리면서 검사하면 코드를 훨씬 짧고 우아하게 만들 수 있습니다.

3. 매개변수 상수 참조 const vector<string>& (공간 복잡도 최적화)

• 문제점: vector<string> babbling으로 받으면, 함수가 호출될 때 원본 배열 전체가 메모리에 통째로 복사됩니다.
• 해결책: const vector<string>& babbling처럼 참조자(&)를 사용하면 복사 없이 원본을 그대로 읽기만 하므로 메모리 사용량을 최소화할 수 있습니다.

---

회고

시간복잡도의 고려는 익숙해졌지만 공간복잡도의 고려를 못한 점이 아쉬웠고, 시간복잡도를 고려하여 가지치기를 하였는데 정작 검사 로직에선 for문을 사용하지 않아 전체적인 부분을 보지 못한점이 아쉬웠다.