[C++] 문자열 substr와 코딩 테스트에서의 활용

앞서 글에서 C++에서 특정 문자를 기준으로 문자열을 자르는 방법에 대해 다루었습니다 (링크).

문자열은 코딩 테스트에서 주요한 카테고리 중 하나로, 그 예시로 카카오 공채 기출문제를 보면 문자열을 다루는 문제들이 많이 나옵니다.

문자열 압축, 괄호 변환, 가사 검색

이번에는 C++의 substr 함수에 대해 다루어 보려고 합니다.

 

C++ 공식 문서에는 다음과 같이 적혀 있습니다:

현재 문자열의 부분 문자열을 기준으로 새로운 문자열을 생성 및 초기화하고 이를 반환한다.

string 변수형의 test 라는 변수가 있고, 내용은 "We study coding test.". 라고 합시다. (string test = "We study coding test.";)

 

test.substr(인자 1, 인자 2) 와 같이 사용합니다.

인자 1은 부분 문자열의 시작 위치를 가리킵니다.

인자 2는 부분 문자열의 길이를 가리킵니다. 공백일 경우 문자열의 끝까지 가리킵니다.

 

다음은 예시입니다.

 

int main() {
    string test = "We study coding test.";

    string t1, t2, t3;
    t1 = test.substr(3, 5);
    //t1 = "study"
    t2 = test.substr(3);
    //t2 = "study coding test."


    size_t pos = test.find("coding");
    t3 = test.substr(pos, 5);
    //t3 = "codin"
}

 

t1은 인자 1이 3, 인자 2가 5인 경우입니다.

인자 3은 study의 s를 가리키고, 이후부터 문자 5개를 가리키므로 "study"가 됩니다.

t2는 마찬가지지만 인자 2가 없으므로, "study coding test."

 

string의 find 함수는 원 문자열에서 해당 부분 문자열이 들어있는 맨 첫 위치를 반환합니다.

예를 들어 위 코드의 경우, coding의 첫 위치인 9를 반환할 것입니다.

이어서 이를 t1과 같이 실행할 경우, c부터 5개의 글자를 반환하므로 t3의 값은 "codin" 이 됩니다.

 

위 코드를 실행한 결과입니다.

 

위 코딩 테스트 문항들에서 사용 예를 살펴 보겠습니다.

 

문자열 압축 문제에서, 주어진 문자열 s = "ababcdcdababcdcd" 라고 합시다.

우리가 할 일은 이 문자열을 각 길이별로 압축해 보는 것입니다.

각 길이를 기준으로 끊어서 본다고 하면, 코드를 다음과 같이 작성할 수 있습니다.

 

int main() {
    string s = "ababcdcdababcdcd";

    for (int i = 1; i < ((int)s.size() / 2) + 1; i++) {
        string tmp = "";
        tmp = s.substr(0, i);

        for (int j = i; j < (int)s.size(); j+=i) {
            string next = s.substr(j, i);
        }
    }
}

 

i는 문자열을 끊어 보는 길이를 나타내고, j는 문자열을 끊는 위치를 나타냅니다.

위 코드에 따르면, 주어진 문자열 s를 i개를 기준으로 끊어냈을 때, 첫 부분 문자열이 tmp에 담기고, 이후 문자열들은 next에 담깁니다.

이를 활용하여 각 문자열을 압축하고, 그 결과를 구할 수 있습니다.

 

괄호 변환 문제에서, 입력받은 문자열 p = "(()())()" 라고 합시다.

이를 균형 잡힌 문자열 u, v로 나눌 때 substr을 활용할 수 있습니다.

 

int main() {
    string p = "(()())()";

    int pos = get_balanced_index(p);
    u = p.substr(0, pos+1);
    v = p.substr(pos+1);
}

 

함수 get_balanced_index는 문자열 u가 균형 잡히게 되는 가장 짧은 경우의 인덱스를 반환하는 함수라고 이해해 주세요.

위 문자열 p에서는 (()())이 좌우 괄호의 갯수가 동일하므로 균형 잡힌 문자열이 됩니다.

이때 균형 잡히게 되는 인덱스는 6번째 인덱스이므로 5가 됩니다.

substr을 이용해 u에는 맨 첫 위치부터 6개의 문자를 잘라내고,

v에는 그 뒤 위치부터 시작해서 끝까지 잘라내는 역할을 기대할 수 있습니다.