split() 함수

split()

split()은 코딩테스트에서 많이 등장하는 로직이다.
split()함수란 다른 프로그래밍 언어에서도 문자열을 특정 문자열을 기준으로 쪼개어서 배열화 시키는 함수이다.
C++에서는 STL에서 split()함수를 지원하지 않는다.
그래서 만들어야 한다.

 

만들어도 시간복잡도는 O(n)이다.

 

예를 들어

aaa bbb ccc

여기 중간에 띄어쓰기(공백)이 있다.

그러면 띄어쓰기를 기반으로 나누어서 배열을 만든다 하면

[aaa, bbb, ccc]이렇게 만들어주는 함수가 split()함수이다.

 

split을 만드는데 있어서 외워야 되는 부분이 있다.

while ((pos = input.find(delimiter)) != string::npos)
{
    token = input.substr(0, pos);;
    ret.push_back(token);
    input.erase(0, pos + delimiter.length());
}

이걸 외워야 하는데

차근차근 해석해보자.

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

 

여기서 보면 input에서 일단 delimiter를 찾는다.

delimiter란 구분문자입니다.

한마디로 우리가 위에서 공백을 기준으로 잘라서 배열로 만들었지 않은가?

그런것을 delimiter라고 한다.

근데 이것을 무한 반복하는데 있어서 찾지 못할 때까지 반복한다.

string::npos란 -1 값을 가지는 상수로 find() 함수 수행 시에 찾는 문자열이 없을 때 반환된다.

 

그렇다면 찾지 못하면 find()함수에서는 -1을 반환하기에 종료가 무한 반복문이 종료가 될 것이다.

결국 input.find(delimiter)를 통해 문자열을 찾는다.

뭐 예를 들어 abcd가 있는데 delimiter가 d이다.

a[0]b[1]c[2]d[3]

그럼 pos에는 3이 들어간다

token = input.substr(0, pos);

 

그럼 3만큼 0에서 3까지 substr을 하기 때문에 abc를 추출한다.

그 다음 

ret.push_back(token);

ret벡터에 token 문자열을 넣어준다.

그리고 앞에서 부터 문자열을 지운다.

예를들어 abcdabc에서 d가 delimiter라면 pos = 3,

delimiter의 사이즈는 1이기 때문에 앞에서 부터 4의 크기의 문자열을 제거해서 abc만 남게 된다.

input.erase(0, pos + delimiter.length());

 

진짜 제대로 설명해보려고 자세히 적었다.

 

그렇다면 진짜 코드를 봐보자.

 

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 = "안녕하세요 저는 산토스라고 합니다. 대충 살고 싶고 대충 개발하고 싶어요.";
	vector<string> a = split(s, " ");
    
    for (string b : a)
    	cout << b << '\n';

	return 0;
}

 

 

 결과물을 봐보자.

 

너무 잘됐따!!!!!!!!!

후 외워

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

 

 

더 빠른 split()도 있다.

 

위에서 설명한 것은 매번 erase()를 하는 단점이 있다.

이를 제거해서 좀 더 빠른 split() 코드는 다음과 같다.

 

vector<string> split(const string& input, string delimiter)
{
    vector<string> result;
    int start = 0;
    int 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;
}