질문있습니다!

2023-06-22T05:52:47.115Z

0

https://www.acmicpc.net/source/62168597

다시 등록했습니다!

0

안녕하세요 동훈님 ㅎㅎ

            str.pop_back();
            str.erase(0,1);
            
           
            dq = split(str,",");

이 부분 말씀하시는거죠?

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

    return ret;
}

어떻게 n^2냐면요. (보통 N^2이라고 보시면 됩니다)

자 앞의 코드를 보면

while ((pos = input.find(deli)) != string::npos){

계속해서 find가 일어납니다. 즉, input을 선형적으로 O(N) 시간복잡도를 가지는 find로 deli를 찾고 있습니다.

이 과정이 최대 N번 일어납니다. input의 길이가 N이라면요.

예를 들어

aaaaa에서 a를 찾는다고 하면

aaaaa

aaaaa

aaaaa

aaaaa

aaaaa

이렇게 N번이 일어나는 것이죠. 정확히는 input.size() / deli.size()이지만 보통의 deli는 input보다 작기 때문에 input.size()인 N이라고 해도 무방합니다.

그렇기 때문에 split() 함수는 N^2 걸리는 것이 자명합니다.

되도록 쓰면 안되는 함수이긴 해요.. ㅠ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.