인프런 커뮤니티 질문&답변

split를 활용했는데 47%까지 가다 메모리 초과가 발생하는데 혹시 이유가 뭔지 궁금합니다 ㅠㅠ

어느 부분이 공간 복잡도를 많이 잡나요?? 재귀적으로 함수를 호출해서 그런가요??

#include <bits/stdc++.h>

using namespace std;

string S, bS;

vector<string> split(string input, string delimiter){
    vector<string> ret;
    long long pos = 0;
    string token = "";
    
    while ((pos = input.find(delimiter))!=string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos+delimiter.length());
        
    }
    
    ret.push_back(input);
    return ret;
    
}

void go(string inputs){
    if(inputs==""){cout << "FRULA"; return;}
    
    vector<string> new_str_v = split(inputs, bS);
    
    if(!new_str_v.empty()){
        if(new_str_v[0] == inputs){
            cout << inputs;
            return;
        }else{
            string new_str = "";
            for(auto i : new_str_v) new_str+=i;
            new_str_v.clear();
            go(new_str);
        }
    }
    
    return;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> S >> bS;
    
    go(S);
    
    
}