C & C++

[C++] 효율적인 문자열 분할(split) 함수 구현

Chunghyun Lee 2024. 7. 9. 13:13

C++ 표준 라이브러리(STL)는 문자열 분할(split) 함수를 기본적으로 지원하지 않습니다. 그러나 문자열을 구분자를 기준으로 분할하는 작업은 많은 프로그래밍 문제에서 자주 요구됩니다. 따라서 우리는 이 작업을 효율적으로 수행할 수 있는 사용자 정의 split 함수를 작성해야 합니다. 이번 글에서는 이를 위한 빠르고 효율적인 split 함수 구현 방법을 소개하고, 상수 참조의 이점과 성능 최적화 기법을 함께 설명합니다.

상수 참조(const reference)란?

  • 참조(reference): C++에서 참조는 특정 변수의 별명을 만들어 줍니다. 즉, 참조는 변수 자체가 아니라 그 변수에 대한 별명입니다.
  • 상수(const): 상수는 값을 변경할 수 없음을 의미합니다. const 키워드는 해당 변수나 객체가 변경되지 않음을 보장합니다.

const string& input은 함수 파라미터로 C++에서 매우 중요한 개념인 상수 참조를 사용하고 있습니다. 이는 함수가 인자로 전달된 문자열을 변경하지 않고, 복사 비용을 피하면서 효율적으로 처리할 수 있게 합니다.

const string& input의 의미

  • const: 함수 내부에서 input을 변경할 수 없도록 보장합니다.
  • string&: input이 string 객체에 대한 참조임을 나타냅니다. 즉, 함수가 string 객체의 복사본을 만드는 대신, 원래 객체를 참조합니다.

왜 상수 참조를 사용하는가?

  1. 효율성: string과 같은 큰 객체를 함수에 전달할 때, 복사본을 만드는 것은 메모리와 시간을 많이 소비할 수 있습니다. 참조를 사용하면 복사 비용을 피할 수 있습니다.
  2. 안전성: const를 사용하면 함수 내에서 원래 객체를 변경할 수 없음을 보장합니다. 이는 함수가 원래 데이터를 보호하는 데 도움이 됩니다.

성능 최적화된 split 함수 구현

기존에 erase 함수를 사용하여 문자열을 분할하는 코드는 다음과 같습니다.

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

이 코드는 erase 함수를 사용하여 문자열에서 분할된 부분을 제거하는 방식으로 동작합니다. 하지만 erase 함수는 문자열의 중간 부분을 제거하고, 나머지 부분을 이동시키는 작업을 포함하므로 성능 저하를 일으킬 수 있습니다.

성능 최적화 코드

erase 함수를 사용하지 않고, start와 end 변수를 사용하여 성능을 최적화한 split 함수는 다음과 같습니다:

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

vector<string> split(const string& input, string delimiter) {
    vector<string> result;
    auto start = 0;
    auto end = input.find(delimiter);
    
    // 구분자가 발견될 때까지 반복
    while(end != string::npos) {
        // start부터 end까지 부분 문자열을 추출하여 result에 추가
        result.push_back(input.substr(start, end - start));
        
        // start를 다음 부분으로 이동
        start = end + delimiter.size();
        
        // 다음 구분자 위치를 찾음
        end = input.find(delimiter, start);
    }
    
    // 마지막 부분 문자열을 result에 추가
    result.push_back(input.substr(start));
    return result;
}

코드 설명

  • 입력 파라미터:
    • const std::string& input: 분할할 원본 문자열입니다. 상수 참조를 사용하여 불필요한 복사를 방지하고, 함수 내에서 원본 문자열이 변경되지 않음을 보장합니다.
    • const std::string& delimiter: 구분자 문자열입니다. 구분자 역시 상수 참조로 전달합니다.
  • 출력:
    • std::vector<std::string>: 분할된 문자열 조각들이 저장된 벡터를 반환합니다.
  • 변수 초기화:
    • size_t start = 0: 분할할 부분 문자열의 시작 위치를 저장합니다.
    • size_t end = input.find(delimiter): 처음 구분자의 위치를 찾습니다.
  • 주요 로직:
    • while (end != std::string::npos): 구분자를 찾을 수 있는 동안 반복합니다.
      • result.push_back(input.substr(start, end - start)): 구분자를 기준으로 잘라낸 부분 문자열을 벡터에 추가합니다.
      • start = end + delimiter.length(): 시작 위치를 다음 부분 문자열의 시작 위치로 이동합니다.
      • end = input.find(delimiter, start): 다음 구분자의 위치를 찾습니다.
    • 반복이 끝난 후 마지막 부분 문자열을 벡터에 추가합니다.

성능 최적화

이 split 함수는 다음과 같은 방법으로 성능을 최적화합니다:

  1. 상수 참조 사용: input과 delimiter를 상수 참조로 전달하여 함수 내부에서 원본 데이터를 복사하지 않도록 합니다.
  2. 메모리 재할당 최소화: result 벡터에 문자열을 추가할 때마다 벡터의 크기가 자동으로 증가하지만, 이는 특정한 패턴을 따라 증가하므로 메모리 재할당 횟수가 최소화됩니다.
  3. 효율적인 문자열 검색: find 메서드를 사용하여 구분자를 빠르게 찾고, substr 메서드를 사용하여 부분 문자열을 효율적으로 추출합니다.
  4. erase 함수 사용하지 않기: erase 함수는 문자열의 중간 부분을 제거하고 나머지 부분을 이동시키는 작업을 포함하므로 성능 저하를 일으킬 수 있습니다. start와 end 변수를 사용하여 직접 문자열의 부분을 추출함으로써 이러한 성능 저하를 방지합니다.

마치며

C++ 표준 라이브러리(STL)에는 문자열 분할을 위한 직접적인 지원이 없지만, 위와 같은 사용자 정의 함수를 통해 이를 쉽게 해결할 수 있습니다. 상수 참조와 효율적인 문자열 검색 방법을 사용하여 성능을 최적화한 split 함수를 작성하면, 다양한 상황에서 유용하게 활용할 수 있습니다.