split() 시간복잡도

16 asked

1

상민님 안녕하세요 ㅎㅎ

상민님의 split()코드가 좀 더 빠르긴 하지만 제가 좀 더 검토해본 결과

한글자(char) 의 경우 잘 되지만

string으로 delimiter를 주는 경우는 잘 되지 않았습니다. + 1로 하기 때문에...

일반화한 코드는 다음과 같습니다.

이걸 쓰시면 될 것같습니다.

vector<string> split(const string& input, string delimiter) {
    vector<string> result; 
    auto start = 0;
    auto end = input.find(delimiter); 
    while (end != string::npos) { 
        result.push_back(input.substr(start, end - start));
        start = end + delimiter.size();
        end = input.find(delimiter, start);
    } 
    result.push_back(input.substr(start)); 
    return result;
}  

1

안녕하세요 상민님 ㅎㅎ

erase를 쓰지 않고 일부분을 찾아서 해당 부분에 대한 시간복잡도를 줄이는 시도는 정말.. 훌륭하네요.

하지만 제가 짠 split() 코드에 생각못한 맹점이 있는지, 이렇게 사용을 해도 되는지 궁금해서 질문올립니다.
>> 네 사용가능할 거 같습니다.

일단 제 코드의 erase 함수 자체가 발동되지 않기 때문에 해당 함수에 대한 코스트자체가 없어지기 때문에 더 좋을 것이라 생각이 듭니다. 다만 char del.. 로 되어있기 때문에 한글자의 문자가 아닌 다른 문자열로 하게 되면 문제가 생기는데요.

그부분 빼고는 정말 괜찮습니다.

일반화한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

string s;

vector<string> split(const string& input, string delimiter) {
    vector<string> result;

    size_t start = 0;
    size_t end = input.find(delimiter);

    while (end != string::npos) {
        result.push_back(input.substr(start, end - start));
        start = end + 1;
        end = input.find(delimiter, start);
    }

    result.push_back(input.substr(start));

    return result;
}

int main(){
    string s = "안녕하세요 큰돌이는 킹갓제너럴 천재입니다 정말이에요!";
    string d = " "; 
    vector<string> a = split(s, d); 
    for(string b : a) cout << b << "\n"; 
} 

상민님의 코드 - 일반화한 코드

그리고

제가 split 코드로 드린 이코드를 비교해봤는데요.

#include <bits/stdc++.h>
using namespace std;  
 
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; 
} 
  
int main(){
    string s = "안녕하세요 큰돌이는 킹갓제너럴 천재입니다 정말이에요!", d = " "; 
    vector<string> a = split(s, d); 
    for(string b : a) cout << b << "\n"; 
} 

내부적으로 78000개 길이정도를 가지는 문자열을 기반으로 간단히 테스트한 결과

상민님의 코드가 제 코드보다 더 좋은 것 같습니다. 한 9배는 빠르네요...

작은 문자열에서는 1ms정도로 차이가 많이 나지는 않지만 1만개이상부터는 확연히 빠른 것을 알 수 있었습니다.

Time taken by function: 26145 microseconds

Time taken by function: 3265 microseconds

테스팅코드는 다음과 같습니다.

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono; 

vector<string> split(const string& input, string delimiter) {
    vector<string> result;

    size_t start = 0;
    size_t end = input.find(delimiter);

    while (end != string::npos) {
        result.push_back(input.substr(start, end - start));
        start = end + 1;
        end = input.find(delimiter, start);
    }

    result.push_back(input.substr(start));

    return result;
}  
// 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; 
// }   

int main() { 
    string s = "";
    for(int j = 0; j < 1000; j++){
        for(int i = 0; i < 26; i++){
            s += char(i + 65);
            s += char(i + 65);
            s += char(i + 65);
            s += " ";
        } 
    }
     
    //string s = "안녕하세요 큰돌이는 킹갓제너럴 천재입니다 정말이에요!";
    string d = " "; 

    // Start timing
    auto start = high_resolution_clock::now();
 
    vector<string> a = split(s, d); 
 
    auto stop = high_resolution_clock::now();
 
    auto duration = duration_cast<microseconds>(stop - start);
 
    cout << "Time taken by function: " << duration.count() << " microseconds" << endl;
 
    // for(const string& b : a) {
    //     cout << b << "\n"; 
    // }
}

해당 부분은 좀 더 검토후 split()에 관한 교안, 강의 부분을 업데이트하도록 하겠습니다.

저보다 더 좋은 코드를 짜는 수강생분은 정말 몇 없는데... 대단하십니다.

감사합니다.

0

제가 답변 확인이 늦었네요
테스팅까지 해보시고 일반화도 해주시다니... 답변 정말 감사합니다.
열심히 고민한 보람이 있는 것 같아요!!!
항상 좋은 강의 감사합니다~

0

안녕하세요 김상민 님, 인프런 AI 인턴이에요.

질문에 제시된 링크의 코드를 확인해보았습니다. 시간 복잡도 개선을 위해 split() 함수를 사용한 구현과 공백을 제외하고 숫자를 세는 방법을 사용한 구현 두 가지를 비교하셨네요.

split() 함수는 문자열을 특정 구분자(기본적으로 공백)를 기준으로 분리하여 문자열 리스트로 반환하는 함수입니다. 이 함수의 시간 복잡도는 일반적으로 O(n)입니다.

첫 번째 링크의 “시간초과 코드”에서는 split() 함수를 사용하여 문자열을 분리하고, 나누어진 문자열 리스트의 길이를 세는 과정을 반복하고 있습니다. 이로 인해 시간 복잡도가 O(n) * O(n) = O(n^2)가 될 수 있습니다.

두 번째 링크의 “통과 코드”에서는 직접 문자열을 순회하면서 공백이 아닌 문자열을 찾아 개수를 세는 방법을 사용하고 있습니다. 이 방법은 split() 함수를 사용하지 않기 때문에 시간 복잡도가 좀 더 개선될 수 있습니다.

따라서, 두 번째 방법과 같이 공백을 제외하고 숫자를 세는 방법을 사용하시는 것이 더 좋은 선택일 수 있습니다. 하지만, split() 함수를 사용한 코드가 절대적으로 잘못된 것은 아니기 때문에 사용하셔도 무방합니다. 다만, 시간 복잡도 개선을 위해서 적절한 로직 수정이나 다른 알고리즘 고려를 해보시는 것도 좋은 방법일 수 있습니다.

추가적인 질문이 있으시면 언제든지 물어보세요! 감사합니다.