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

06 Feb 2023 in Study on Coding Test

백트래킹을 이용하려다가 실패한 문제, erase를 활용하는 문제

정답제출코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string s_prev = "";

int solution(vector<string> babbling) {
    int answer = 0;
    
    int len = babbling.size();
    
    for (int i = 0; i < len; ++i)
    {
        int len_word = babbling[i].length();
        string s = "";
        s_prev = "";
        
        for (int j = 0; j < len_word; ++j)
        {
            // babbling에 포함되어있지 않은문자가 나타날경우 break
            if (babbling[i][j] != 'a' && babbling[i][j] != 'y' && babbling[i][j] != 'e'
               && babbling[i][j] != 'o' && babbling[i][j] != 'm' && babbling[i][j] != 'w')
                break;
            else
            {
                s += babbling[i][j];
            }
            
            // 검증용
            // cout << s << '\n';
            
            if (s == "aya" || s == "ye" || s == "woo" || s == "ma")
            {
                if (s != s_prev)
                {
                    //추출
                    babbling[i].erase(0, s.length());
                    s_prev = s;
                    s = "";
                    
                    // -1을 지정한 다음에 ++j가 진행되어 인덱스가 0으로 돌아감.
                    j = -1;
                }
                else
                {
                    break;
                }
            }
        }
        // 검증용
        // cout << babbling[i] << '\n';
        // cout << '\n';
        
        if (babbling[i].length() == 0)
            answer++;
    }
    
    return answer;
}

문자열을 저장할 공간을 주고, 문자열에 하나씩 문자를 쌓아가며 일치하는 문자열이 나올 때마다 소거를 해서 마지막에 문자열에 문자가 하나도 없을 때 answer를 1씩 더하는 방식을 채택했다.

오답제출코드 (시간초과)

#include <string>
#include <vector>

using namespace std;

int answer_st = 0;
string bab[4] = {"aya", "ye", "woo", "ma"};

void backtrack(string s, string i, int _index)
{
    if (s.length() > 30)
        return;
    else if (s == i)
    {
        answer_st++;
        return;
    }
    
    for (int j = 0; j < 4; ++j)
    {
        if (j == _index)
            continue;
        string tmp = s + bab[j];
        backtrack(tmp, i, j);
    }
}

int solution(vector<string> babbling) {
    int answer = 0;
    int len = babbling.size();
    
    for (int i = 0; i < len; ++i)
    {
        string s = babbling[i];
        for (int j = 0; j < 4; ++j)
        {
            backtrack(bab[j], s, j);
        }
    }
    
    answer = answer_st;
    return answer;
}

지난 옹알이 (1) 문제에서는 옹알이당 최대 길이가 15이었기 떄문에 백트래킹이 통했지만

이번 문제는 최대 30이었기 때문에 통하지 않았다.

결국 시간초과떴다.

이전에 옹알이 (1) 문제를 풀 때 동료분과 같이 풀었었는데,

동료분은 해당 문자열을 소거하는 방식으로 푸셨었다.

출제자의 의도도 아마 이렇지 않았을까? 생각하며 C++에서 문자열을 소거하는 방법을 찾아보았다.

그리고 erase를 활용하기로 했다.