Featured image of post [Algorithm] C++/Python 백준 16163번 : 회문 부분 문자열 세기
Algorithm String Palindrome

[Algorithm] C++/Python 백준 16163번 : 회문 부분 문자열 세기

문자열의 부분 문자열 중 회문(Palindrome)이 몇 개인지를 구하는 문제는 문자열 알고리즘에서 자주 볼 수 있는 중요한 유형이다. 특히 긴 문자열에 대해 효율적으로 풀기 위해서는 고전적인 O(N^2) 접근 대신, 복잡도를 줄일 수 있는 알고리즘을 활용해야 한다. 이번 포스팅에서는 ‘Manacher 알고리즘’을 통해 문제를 해결하는 방식을 소개하고자 한다. Manacher 알고리즘은 문자열 전처리를 통해 모든 중심에 대해 팰린드롬의 반경(길이)을 O(N) 시간에 구할 수 있기 때문에, 팰린드롬 부분 문자열의 개수를 빠르게 계산할 수 있다.

문제 : https://www.acmicpc.net/problem/16163

문제 설명

문제의 요구 사항은 간단해 보이지만, 문자열의 길이가 최대 수백만에 이를 수 있어 단순한 이중 반복문(O(N^2))으로는 시간 초과가 발생하기 쉽다. 구체적으로 문제에서 주어지는 문자열을 확인하고, 이 문자열 내의 ‘연속된’ 부분 문자열 중에서 회문이 되는 경우의 수를 전부 세어야 한다는 점이 핵심이다. 여기서 ‘부분 문자열(Substring)’은 문자열에서 연속된 위치를 차지하는 것으로, 부분 수열(Subsequence)과는 구분되는 개념임에 유의해야 한다.

실제 문제에서는 알파벳 대문자로만 구성된 긴 문자열이 주어질 수 있으므로, 우리가 고려해야 하는 후보 부분 문자열의 개수는 최대 \(\frac{N(N+1)}{2}\)개가 된다. 예를 들어 길이가 N인 문자열이 주어졌다면, 가능한 부분 문자열은 길이 1짜리 N개, 길이 2짜리 N-1개, … 길이 N짜리 1개 등 총합이 \(\frac{N(N+1)}{2}\)개이다. 이 중 어떤 부분 문자열이 회문인지 판단하기 위해 매번 양끝에서부터 비교하게 되면 O(N^3)까지도 치솟을 수 있고, 이 방식으로는 대규모 데이터를 처리하기가 어렵다.

이에 대한 효율적인 해결책으로 Manacher 알고리즘이 등장한다. Manacher 알고리즘의 주요 아이디어는 문자열 사이에 구분자(예: ‘#’)를 삽입해 홀수 길이와 짝수 길이의 팰린드롬 처리를 통일시키고, 각 인덱스를 ‘중심’으로 하는 팰린드롬의 최대 ‘반지름’을 빠르게 구하는 방식이다. 이를 통해 모든 부분 문자열이 팰린드롬인지 확인하지 않고도, 각 위치별로 가능한 팰린드롬의 개수를 합산하여 결과를 얻을 수 있다.

종합적으로 정리하자면, 문제에서 요구하는 것은 “주어진 문자열에서 연속된 부분 문자열 중 회문인 것이 몇 개인가”를 빠르게 계산하는 일이다. 이 때 Manacher 알고리즘을 활용하여 O(N) ~ O(N+1) 정도의 시간 복잡도로 각 위치를 중심으로 하는 최대 팰린드롬 반지름을 구하고, 그것을 합산해 최종적인 회문 부분 문자열 수를 구하게 된다. 이 접근 방식은 크게 다음과 같은 과정으로 요약할 수 있다.

  1. 문자열 전처리: 구분자 삽입.
  2. Manacher 알고리즘으로 각 중심에 대한 팰린드롬 반경 계산.
  3. 팰린드롬 개수 환산: 각 중심의 팰린드롬 반경을 합산.

위 과정을 통해 문제에서 요구하는 모든 회문 부분 문자열의 개수를 효율적으로 구할 수 있다.

접근 방식

  1. 문자열 전처리
    문자열의 각 문자 사이에 구분자(주로 ‘#’)를 삽입함으로써, 모든 팰린드롬을 ‘홀수 길이’ 형태로 통일한다. 이렇게 하면 짝수 길이인 경우에도 가운데 구분자를 중심으로 생각할 수 있으므로, 별도의 추가 처리가 필요 없어지는 장점이 있다.

  2. Manacher 알고리즘

    • 각 인덱스를 중심으로 하는 팰린드롬 반지름을 구하는 과정을 O(N) 안에 처리한다.
    • 이미 구한 반지름 정보를 활용하여, 새로운 중심을 설정할 때 중복 계산을 최소화한다.
    • 각 위치에서 팰린드롬을 확장할 때, 기존에 구해둔 정보를 적극적으로 재활용한다.

  3. 팰린드롬 개수 계산

    • 변환된 문자열에서 구한 팰린드롬 반지름 p[i]는 구분자가 포함된 문자열 기준의 길이이다.
    • 이를 원본 문자열에 대응하기 위해 \((p[i] + 1) / 2\)를 취해 더한다.
    • 마지막으로 이 값을 모두 합산하면, 원본 문자열에서의 회문 부분 문자열 개수가 산출된다.

C++ 코드와 설명

아래 코드는 Manacher 알고리즘을 적용해 문제를 해결한 최적화된 예시 C++ 코드이다. 각 라인에 주석을 달아 동작을 상세히 설명하겠다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

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

// Manacher 알고리즘을 사용해 문자열에서 부분 문자열 중
// 팰린드롬인 것의 총 개수를 O(N) 복잡도로 구하는 예시 코드이다.

// 문자열 s를 입력받아 회문 부분 문자열의 총 개수를 반환하는 함수이다.
long long countPalindromes(const string &s) {
    // 1. 구분자 '#'을 삽입한 문자열 T를 만든다.
    //    예: "ABC" -> "#A#B#C#"
    string T;
    T.push_back('#');
    for (char c : s) {
        T.push_back(c);
        T.push_back('#');
    }

    // 2. 변환 문자열 T의 길이 n과,
    //    각 위치에서의 팰린드롬 '반지름' 값을 저장할 p 배열을 선언한다.
    int n = (int)T.size();
    vector<int> p(n, 0);

    // 3. center와 right는 팰린드롬 중심과
    //    해당 중심 기준으로 가장 오른쪽으로 뻗어 있는 범위를 나타낸다.
    int center = 0, right = 0;
    long long result = 0;

    // 4. Manacher 알고리즘 메인 루프
    for (int i = 0; i < n; i++) {
        // mirror는 i에 대해 center 기준 반대편 인덱스이다.
        int mirror = 2 * center - i;

        // i가 right 범위 내에 있다면, p[i]의 초기값을
        // mirror의 p값과 (right - i) 중 작은 값으로 설정한다.
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }

        // 5. i를 중심으로 좌우를 확장하며 팰린드롬 길이를 갱신한다.
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && T[i - p[i] - 1] == T[i + p[i] + 1]) {
            p[i]++;
        }

        // 6. 새로 구한 팰린드롬이 right 경계를 넘어선다면,
        //    center와 right를 갱신한다.
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        // 7. result에 (p[i] + 1) / 2를 더한다.
        //    (p[i] + 1) / 2는 원본 문자열에서의 팰린드롬 개수에 해당한다.
        result += (p[i] + 1) / 2;
    }

    // 8. 모든 중심에서의 값을 더한 result가 곧
    //    주어진 문자열 s에서의 회문 부분 문자열의 총 개수이다.
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    cout << countPalindromes(s) << "\n";
    return 0;
}

코드 동작 단계별 설명

  1. 입력 및 전처리
    • 입력받은 문자열 s에 대하여 앞뒤와 문자 사이사이에 구분자(#)를 삽입해 T를 만든다.
  2. p 배열과 변수 초기화
    • p 배열은 각 위치에서 팰린드롬 확장 길이를 저장한다.
    • center, right는 현재까지 발견된 팰린드롬이 미치는 범위를 결정짓는다.
  3. 반복문을 통한 Manacher 알고리즘 실행
    • mirror 값으로 기존에 계산된 값을 재활용해 중복 계산을 줄인다.
    • 중심을 기준으로 좌우로 확장해 팰린드롬 길이를 갱신한다.
    • 확장 결과가 right를 넘어서면 center와 right를 재설정한다.
  4. 결과 계산
    • result에 각 위치에서 \((p[i] + 1) / 2\)를 합산해 원본 문자열의 회문 부분 문자열 총 개수를 구한다.

Python 코드와 설명

아래는 동일한 로직을 Python으로 구현한 최적화 버전이다. C++ 코드와 마찬가지로 Manacher 알고리즘을 활용해 O(N) 복잡도로 결과를 도출한다. 각 라인에 주석을 달아 동작을 상세히 설명하였다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def count_palindromes(s):
    # 1. 구분자 '#'을 삽입한 문자열 T를 만든다.
    #    예: "ABC" -> "#A#B#C#"
    T = '#' + '#'.join(s) + '#'
    
    n = len(T)
    p = [0] * n  # 각 위치에서 팰린드롬 '반지름'을 저장할 리스트
    center = 0
    right = 0
    result = 0
    
    # 2. Manacher 알고리즘으로 팰린드롬 길이 계산
    for i in range(n):
        mirror = 2 * center - i  # i에 대해 center 기준 반대편 인덱스

        if i < right:
            p[i] = min(right - i, p[mirror])
        
        # 3. 중심 i에서 좌우 확장
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n \
              and T[i - p[i] - 1] == T[i + p[i] + 1]:
            p[i] += 1
        
        # 4. 팰린드롬이 오른쪽 경계를 넘으면 center, right 업데이트
        if i + p[i] > right:
            center = i
            right = i + p[i]
        
        # 5. (p[i] + 1) // 2를 더해 원본 문자열에서의 회문 개수 반영
        result += (p[i] + 1) // 2
    
    return result

def main():
    import sys
    input_str = sys.stdin.readline().strip()
    print(count_palindromes(input_str))

if __name__ == "__main__":
    main()

코드 동작 단계별 설명

  1. 구분자 삽입
    • Python의 join 함수를 이용해 원본 문자열의 문자 사이에 #을 삽입한다.
  2. 배열 및 변수 초기화
    • p는 각 인덱스에서의 팰린드롬 반지름을 저장한다.
    • center와 right는 현재 검사 중인 팰린드롬이 커버하는 구간을 나타낸다.
  3. 반복문
    • 인덱스 i에 대해 mirror 인덱스(2 * center - i)의 p 값을 참조해 초기값을 설정한다.
    • 문자가 좌우 대칭이면 확장하며 p[i]를 갱신한다.
  4. 결과 도출
    • 각 위치의 p[i] 값을 합산하여 최종 결과를 구한다.

결론

이 문제는 문자열의 부분 문자열 중 회문인 것을 모두 세어야 하므로, 단순 이중 반복문을 사용한 방식은 긴 문자열에서 시간 초과가 발생하기 쉽다. 따라서 Manacher 알고리즘을 통해 O(N)에 가까운 시간에 각 인덱스 중심 팰린드롬의 길이를 계산하고, 이를 합산하는 방식이 유효함이다. 이를 통해 긴 문자열에 대해서도 충분히 빠른 시간 안에 정답을 도출할 수 있다. 추가적으로, 구분자 외에 특수 문자를 사용하는 등 다양한 구현상의 변형이 가능하지만, 핵심 로직은 동일하다. 이 문제를 풀며 문자열 알고리즘에서 전처리와 효율적 계산 기법을 잘 이해하고 활용하는 것이 중요하다는 점을 다시금 깨닫게 되었다.