프로그래머스 옹알이 토큰 매칭 구현

문자열을 앞에서부터 토큰으로 갉아먹는 문제를 풀었는데, 알고리즘이 틀린 게 아니라 실패 판정을 놓는 위치가 틀려서 답이 어긋났다. 이 글에서는 옹알이 문제의 구현을 따라가며 그 지점을 이야기하려 한다 — 구현은 토큰 소비 루프와 사용 여부 플래그, 트러블슈팅은 string::compare 시그니처 오해와 조기 실패 판정 두 건이다.

문제 — 옹알이(aya, ye, woo, ma)

각 발음(“aya”, “ye”, “woo”, “ma”)을 최대 1번씩만 사용해 단어를 만들 수 있을 때, 발음 가능한 단어 개수를 구하는 문제다.

트러블슈팅 — 토큰을 다 보기 전에 실패로 빠진다

원인: match 실패 판정을 토큰 순회 for 안쪽에 둔 것. 토큰 네 개 중 첫 번째가 안 맞는 순간 실패로 확정되니, 두 번째 이후 토큰은 확인조차 되지 않는다. 여기에 string::compare의 시그니처를 잘못 알고 있어 비교 자체가 의도와 다르게 동작한 것이 겹쳤다.

증상: "wooye"처럼 앞 토큰이 “aya”가 아닌 단어들이 전부 불가 판정으로 떨어져, 정답보다 개수가 적게 나왔다.

해결: 실패 판정을 토큰 for를 완전히 빠져나온 뒤로 옮겨 if (!match)를 while 본문 끝에서 검사하게 했다. 비교는 word.compare(pos, len, token[j]) == 0 — pos부터 len글자를 token과 견주는 3인자 오버로드로 고정했다. 순회는 복사 비용이 없는 const string& 범위 기반 for로 정리했다.

기술 구현 — pos 포인터로 소비하는 토큰 매칭

고친 기본형이 아래 코드다. pos 포인터가 왼쪽부터 문자열을 소비하고, used 플래그가 각 발음의 1회 제한을 건다.

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

    // range-based for: babbling의 각 단어를 복사 없이(const reference) 순회
    for (const string& word : babbling) {
        vector<bool> used(4, false); // 각 발음은 최대 1번만 사용
        int pos = 0;                 // 현재 읽는 위치(왼쪽부터 소비)
        bool ok = true;

        // while 사용 이유: 단어 길이 끝까지 pos를 전진시키며 확인
        // (시간복잡도는 단어 길이 L에 비례, 전체 O(N * L * 4))
        while (pos < (int)word.size()) {
            bool match = false;

            for (int j = 0; j < (int)token.size(); j++) {
                int len = (int)token[j].size();

                // compare(pos, len, token[j]) == 0 :
                // word의 pos부터 len글자가 token[j]와 같으면 매칭
                if (!used[j] &&
                    pos + len <= (int)word.size() &&
                    word.compare(pos, len, token[j]) == 0) {
                    used[j] = true;
                    pos += len;      // 매칭된 길이만큼 이동
                    match = true;
                    break;
                }
            }

            // 토큰 전체를 다 확인한 뒤에도 매칭이 없을 때만 실패
            if (!match) {
                ok = false;
                break;
            }
        }

        // 카운트 증가 시점: '단어 하나' 검증이 끝난 뒤에만 증가
        if (ok && pos == (int)word.size()) {
            answer++;
        }
    }

    return answer;
}

복습하면서 유효 단어 목록과 개수를 함께 출력하는 버전도 만들어 봤다. 로직은 같고, 통과한 단어를 validWords에 모아 마지막에 출력하는 부분만 다르다.

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

    for (const string& word: babbling) {
        vector<bool> used(4,false);
        int pos = 0;
        bool ok = true;

        while (pos < (int)word.size()) {
            bool match = false;
            for (int j = 0; j < (int)token.size(); j++) {
                int len = (int)token[j].size();
                if (!used[j] &&
                    pos + len <= (int)word.size() &&
                    word.compare(pos, len, token[j]) == 0) {
                    used[j] = true;
                    pos += len;
                    match = true;
                    break;
                }
            }
            if (!match) {
                ok = false;
                break;
            }
        }

        if (ok && pos == (int)word.size()) {
            answer++;
            count++;
            validWords.push_back(word);
        }
    }

    for (int i = 0; i < (int)validWords.size(); i++) {
        cout << validWords[i] << endl;
    }
    cout << count << endl;

    return answer;
}

int main() {
    vector<string> test = {"yewoo", "wooye", "mayeaya", "ayawooma", "woowoo", "aya"};
    cout << solution(test) << endl;
    return 0;
}

정리하면 핵심은 pos 포인터로 문자열을 끝까지 소비하며 토큰을 매칭하는 것이고, used 배열로 각 발음의 1회 제한을 건다. 복잡도는 O(N × L × 4) 수준이라 제한 안에서 안정적이다.

핵심 요약 — 문자열 토큰 매칭은 pos 포인터로 왼쪽부터 소비하며 word.compare(pos, len, token)으로 비교하고, used 플래그로 사용 횟수 제한을 건다. 실패 판정은 토큰 전체를 확인한 뒤에만 내려야 조기 실패를 막을 수 있다.