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

안녕하세요, 큰돌님!

교안에서 제시된 내용을 기반으로 알고리즘 문제를 풀다가 궁금한 부분이 생겨 질문드렸습니다.

교안에서 제시된 문자열 - split 함수는 아래와 같습니다.

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;
}

저는 위 함수를 응용하거나 문제를 해결하는데, 오늘 백준의 5430번 문제를 해결할 때도 위와 같은 로직의 코드를 작성하여 문자열 split을 시도하였습니다.

// I-2. 각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. 
cin >> _p;
// I-3. 다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. 
cin >> _n;
// I-4. 다음 줄에는 [x1, ... xn]과 같은 형태로 배열에 들어있는 정수가 주어진다.
cin >> _x; 
	
string origin = _x.substr(1, _x.size() - 2);
vector<string> vs_x(_n);
if(origin.empty())
{
	
}
else
{
	int pos = 0;
	int cycle = 0;
	while((pos = origin.find(',')) != string::npos)
	{
		string tmp = origin.substr(0, pos);
		vs_x[cycle++] = tmp;
		origin.erase(0, pos + 1);
	}
	vs_x[cycle] = origin;
}	 

코드에 대해 부연설명을 드리자면, 입력을 통해 문자열을 받게 되면, 해당 문자열의 첫번째와 마지막 인덱스를 제외한 문자열을 origin에 저장한 후, 이 문자열 origin을 컴마(,)를 기준으로 split 하였습니다. 예를 들어, [1, 2, 3]이라는 문자열을 입력(_x)으로 받았다면, 변수 origin에 1,2,3을 저장한 후 컴마를 기준으로 문자열을 split할 수 있습니다.

하지만, 위 코드와 함께 문제를 해결하고자 할 때, 지속적으로 시간 초과 문제가 발생하였습니다. 따라서 split 함수를 다음과 같은 로직으로 변경한 후 답안을 다시 제출하였으며, 그 결과 시간 초과가 발생하지 않고 문제를 해결할 수 있었습니다.

// I-2. 각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. 
cin >> _p;
// I-3. 다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. 
cin >> _n;
// I-4. 다음 줄에는 [x1, ... xn]과 같은 형태로 배열에 들어있는 정수가 주어진다.
cin >> _x; 

string token = "";
vector<string> vs_x(_n);
int cycle = 0;
		
for(int j = 0; j < _x.length(); ++j)
{
	if(isdigit(_x[j]))
	{
		token += _x[j];
	}		
	else
	{
		if(!token.empty())
		{
			vs_x[cycle++] = token;
			token = "";
		}
	}
}	

제가 궁금한 것은 위에 제시된 split에 대한 두 개의 로직이 왜 효율성 차이가 나는지 잘 모르겠습니다.. origin.erase(0, pos + 1)이 O(n)의 시간 복잡도를 요구하면서, 첫 번째 로직은 O(n^2)의 시간 복잡도와 두 번째 로직은 O(n)의 시간 복잡도를 필요로 할 수도 있겠다는 생각이 들기도 하지만, 정확하게 어떤 부분이 큰 차이를 불러 일으키는지 잘 모르겠습니다. 감사합니다!