[C++] 문자열 처리 - 연속된 문자열과 동일한 문자열 (1)

문자열 처리

개요

　연속된 문자열과 동일한 문자열을 처리하는 것은 다양한 문제 해결에 필수적인 요소 중 하나다. 문자열 내에서 동일하거나 연속적인 문자나 패턴을 식별하고 처리하는 능력은 데이터 압축, 정보 검색, 보안 강화 등 여러 분야에서 중요한 역할을 한다. 특히, 연속된 문자열은 예측이 쉬우므로 보안 문제에서 취약점으로 작용할 수 있으며, 반면에 동일한 문자열은 데이터의 중복을 나타내므로 압축 알고리즘에서 핵심 요소로 작용한다. 이러한 문자열 처리 기법은 컴퓨터 과학과 프로그래밍의 여러 분야에서 활용되며, 효율적인 알고리즘과 메서드를 통해 더 나은 성능과 결과를 얻을 수 있다. 이번 시간에는 이러한 문자열을 처리하는 방법에 대해 알아보도록 하자.

---

본문

연속된 문자열

　연속된 문자열은 abc, 123처럼 문자나 숫자가 순차적으로 나열되어 있는 경우를 의미한다. 이를 감지하는 함수를 정규식 라이브러리 regex를 이용하는 방법과 문자열을 순회하는 방법, 슬라이딩 윈도 기법을 통해 구현해 보도록 하겠다.

 

regex 이용

#include <iostream>
#include <string>
#include <regex>

bool IsConsecutive(const std::string& str)
{
    std::regex alpha_pattern("abc|bcd|cde|def|efg|hij|jkl|mno|pqr|rst|tuv|uvw|wxy|xyz");
    std::regex number_pattern("012|123|234|345|456|567|678|789");

    return std::regex_search(str, alpha_pattern) || std::regex_search(str, number_pattern);
}

int main()
{
    std::string str;
    std::getline(std::cin, str);

    if (IsConsecutive(str))
        std::cout << str << " is consecutive string\n";

    else
        std::cout << str << " is not consecutive string\n";

    return 0;
}

 

　regex 라이브러리를 이용해 정규 패턴을 만든 후 regex_search()를 통해 해당 문자열이 매칭되는지 확인하게 구현하였다. regex 라이브러리에 대한 설명은 이 게시글에서 한 번 다루었으니, 참고하도록 하자. 해당 함수의 시간 복잡도는 입력 문자열의 길이를 n이라 할 때, O(n)의 시간 복잡도를 가진다. 

 

문자열 순회

#include <iostream>
#include <string>

bool IsConsecutive(const std::string& str)
{
    for (int i = 1; i < str.length(); ++i)
    {
        if (str[i] - str[i - 1] != 1)
            return false;
    }

    return true;
}

int main()
{
    std::string str;
    std::getline(std::cin, str);

    if (IsConsecutive(str))
        std::cout << str << " is consecutive string\n";

    else
        std::cout << str << " is not consecutive string\n";

    return 0;
}

 

　문자열을 순회하며 각 문자의 ASCII 값의 차이를 이용하여 연속된 문자열을 감지하는 함수다. 예를 들어 b의 ASCII 값에서 a의 ASCII 값을 빼면 1이 되고, 1과 2가 입력되었을 때도 1이 되므로 연속된 문자열이라고 판단하게 된다. 이 방법 또한 문자열 길이 n에 대해 O(n)의 시간 복잡도를 갖는다. 

 

슬라이딩 윈도우(Sliding window)

#include <iostream>
#include <string>

bool IsConsecutive(const std::string& str) 
{
    for (int i = 0; i < str.length() - 1; ++i) 
    {
        // 연속된 문자열을 찾기 위한 윈도우 크기는 2
        char curr = str[i];
        char next = str[i + 1];

        // 연속된 문자나 숫자를 찾는 경우
        if (next - curr != 1) 
            return false;
    }

    return true;
}

int main()
{
    std::string str;
    std::getline(std::cin, str);

    if (IsConsecutive(str))
        std::cout << str << " is consecutive string\n";

    else
        std::cout << str << " is not consecutive string\n";

    return 0;
}

 

　슬라이딩 윈도우 기법이란 배열이나 리스트의 서브셋을 연속적으로 관찰하는 알고리즘 디자인 패턴이다. 이 기법은 주로 연속적인 데이터 구조 내에서 특정 조건을 만족하는 부분 집합을 찾거나 그런 부분들을 처리할 때 사용된다. 이때 두 개의 포인터를 사용하여 데이터 구조를 효율적으로 순회한다. 즉, 이 두 포인터가 윈도를 형성하며, 윈도의 크기는 고정되거나 동적으로 조정될 수 있다.

• 해당 기법에 대해서는 추후에 자세히 다루도록 하겠다.

 

　이 함수는 주어진 문자열 내에서 문자가 연속적인지 확인하기 위해 현재 위치(curr)와 다음 위치(next) 문자를 이용한다. 각 문자 위치에서, 현재 문자와 바로 다음 문자 사이의 ASCII 값의 차이를 계산하여 이 값이 1인지 확인한다. 

 

　앞서 설명한 문자열 순회 부분과 매우 유사하지만, 코드의 작성 방식과 구조에 차이가 있다. 슬라이딩 윈도 방식에서는 연속성을 확인하기 위해 명시적으로 현재 위치와 다음 위치의 문자를 구분하여 사용하는 반면, 문자열 순회 방식에서는 인덱스를 기반으로 이전 문자와 현재 문자를 비교한다. 이러한 접근 방식의 차이는 개발자의 코딩 스타일이나 문제의 요구사항에 따라 선택될 수 있다. 슬라이딩 윈도 방식은 윈도의 크기나 범위를 동적으로 조절해야 하는 복잡한 문제에서 더 유용할 수 있으며, 순회 방식은 코드의 간결성과 직관성이 중요할 때 적절하다.