프로그래머스 [연습문제 / 옹알이](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 133499 옹알이 (2)

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/133499

문제 설명:

11개월 된 조카는 "aya", "ye", "woo", "ma" 네 가지 발음만 할 수 있으며, 이를 조합하여 단어를 만들 수 있습니다. 단, 같은 발음을 연속해서 하는 것은 어려워합니다. 문자열 배열 babbling이 주어질 때, 조카가 발음할 수 있는 단어의 개수를 구하는 문제입니다. 문자열 파싱과 상태 추적을 활용한 구현 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>
using namespace std;

int solution(vector<string> babbling) {
    int answer = 0;
    
    // 발음 가능한 단어 목록
    vector<string> words = {"aya", "ye", "woo", "ma"};
    
    // 각 단어에 대해 검사
    for(const string& s : babbling) {
        bool canSpeak = true;      // 발음 가능 여부
        string lastWord = "";       // 마지막으로 발음한 단어
        int pos = 0;                // 현재 검사 위치
        
        // 문자열을 끝까지 파싱
        while(pos < s.length()) {
            bool found = false;
            
            // 네 가지 발음 중 하나와 매칭되는지 확인
            for(const string& word : words) {
                int wordLen = word.length();
                
                // 현재 위치에서 발음 가능한 단어인지 확인
                if(pos + wordLen <= s.length() && 
                   s.substr(pos, wordLen) == word) {
                    
                    // 연속된 발음인지 체크
                    if(lastWord == word) {
                        canSpeak = false;
                        break;
                    }
                    
                    // 발음 성공
                    lastWord = word;
                    pos += wordLen;
                    found = true;
                    break;
                }
            }
            
            // 매칭되는 발음이 없으면 발음 불가
            if(!found) {
                canSpeak = false;
                break;
            }
            
            // 연속 발음 체크에서 걸렸으면 중단
            if(!canSpeak) break;
        }
        
        // 문자열을 모두 소진하고 발음 가능하면 카운트
        if(canSpeak) answer++;
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 문자열 파싱과 상태 추적을 활용합니다. 각 단어를 앞에서부터 순회하며, 발음 가능한 네 가지 단어("aya", "ye", "woo", "ma") 중 하나와 매칭되는지 확인합니다. 매칭된 단어가 직전에 발음한 단어와 같으면 연속 발음으로 판단하여 발음 불가 처리합니다. 문자열을 끝까지 소진하고 모든 조건을 만족하면 발음 가능한 단어로 카운트합니다.
• 구현 세부사항:
  • words 벡터에 발음 가능한 네 가지 단어를 저장합니다.
  • 각 단어를 순회하며 pos 변수로 현재 검사 위치를 추적합니다.
  • substr 함수로 현재 위치에서 발음 가능한 단어와 매칭되는지 확인합니다.
  • lastWord 변수로 이전에 발음한 단어를 저장하여 연속 발음을 체크합니다.
  • 매칭되는 발음이 없거나 연속 발음이면 canSpeak를 false로 설정합니다.
  • 문자열을 끝까지 파싱했고 canSpeak가 true이면 카운트를 증가시킵니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n ⋅ m ⋅ k)입니다. 여기서 n은 babbling 배열의 길이, m은 각 문자열의 평균 길이, k는 발음 가능한 단어 개수(4개)입니다. 각 문자열의 모든 위치에서 4개의 단어와 비교하므로 이러한 복잡도가 나옵니다. 공간 복잡도는 O(1)로, 고정된 크기의 추가 메모리만 사용합니다.

---

실행 예시

테스트 케이스 1:

입력: babbling = ["aya", "yee", "u", "maa"]

실행 과정:

• "aya": "aya"와 매칭 → 발음 가능 ✓
• "yee": "ye"와 매칭 후 "e" 남음 → 발음 불가 ✗
• "u": 매칭되는 발음 없음 → 발음 불가 ✗
• "maa": "ma"와 매칭 후 "a" 남음 → 발음 불가 ✗

출력: 1

테스트 케이스 2:

입력: babbling = ["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]

실행 과정:

• "ayaye": "aya" + "ye" → 발음 가능 ✓
• "uuu": 매칭되는 발음 없음 → 발음 불가 ✗
• "yeye": "ye" + "ye" (연속 발음) → 발음 불가 ✗
• "yemawoo": "ye" + "ma" + "woo" → 발음 가능 ✓
• "ayaayaa": "aya" + "aya" (연속 발음) → 발음 불가 ✗

출력: 2

---

결과

문자열 파싱과 상태 추적을 통해 효율적으로 문제를 해결했습니다. 원본 코드는 각 문자를 하나씩 체크하는 방식이었지만, 리팩토링된 코드는 발음 가능한 단어 목록을 배열로 관리하여 가독성과 유지보수성을 크게 향상시켰습니다. substr을 활용한 문자열 비교로 코드가 간결해지고, 연속 발음 체크 로직도 더 명확해졌습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!