11월 7일 - #15164번_제보[BOJ/16163]

주어진 문자열의 부분 문자열 중 회문인 것의 개수를 구하는 문제를 풀어봤다. 이 문제는 문자열 길이가 최대 200만까지 가능하므로 모든 부분 문자열을 탐색하는 브루트포스 방식으로는 시간 초과가 발생할 수 있다. 그래서 Manacher's 알고리즘을 활용해 문제를 해결했다. Manacher's 알고리즘은 문자열에서 모든 회문의 길이를 O(n)의 시간 복잡도로 찾을 수 있는 효율적인 알고리즘이다.

문제 접근 방법

1. Manacher's 알고리즘을 활용하여 회문을 탐색:

• Manacher's 알고리즘은 회문의 중심을 기준으로 확장하면서 회문의 길이를 찾는 방식이다.
• 중심 대칭을 이용해 이미 계산된 정보를 활용하므로 시간 복잡도를 O(n)으로 줄일 수 있다.

2. 문자 사이에 특수 문자 삽입:

• Manacher's 알고리즘은 회문의 중심이 항상 한 글자인 경우에 유리하다.
• 문자열의 각 문자 사이에 # 같은 특수 문자를 삽입하여 짝수 길이의 회문도 모두 홀수 길이로 변환했다.

3. 각 중심에서 회문의 길이를 구하고 누적 합계 계산:

• 각 중심에서 회문의 길이를 구하고 그 길이에 따라 회문 개수를 누적하여 총 회문 개수를 계산했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine().trim();
        
        // 문자열을 #으로 구분하여 새로운 문자열 생성
        StringBuilder sb = new StringBuilder("#");
        for (char c : input.toCharArray()) {
            sb.append(c).append("#");
        }
        String modifiedString = sb.toString();

        System.out.println(manachers(modifiedString));
    }

    public static long manachers(String s) {
        int n = s.length();
        int[] A = new int[n]; // 각 중심에서 확장되는 회문의 길이를 저장하는 배열
        int r = 0, p = 0;     // r: 가장 오른쪽까지 뻗은 회문의 끝, p: 그 중심
        long result = 0;      // 총 회문 개수

        for (int i = 0; i < n; i++) {
            // 회문의 길이 대칭성 활용
            if (i <= r) {
                A[i] = Math.min(A[2 * p - i], r - i);
            }

            // 회문 확장
            while (i - A[i] - 1 >= 0 && i + A[i] + 1 < n && s.charAt(i - A[i] - 1) == s.charAt(i + A[i] + 1)) {
                A[i]++;
            }

            // 가장 오른쪽 회문 업데이트
            if (r < i + A[i]) {
                r = i + A[i];
                p = i;
            }

            // 각 중심에서 구해진 회문의 절반 크기만큼 회문 개수를 누적
            result += (A[i] + 1) / 2;
        }
        
        return result;
    }
}

코드 설명

1. 문자 사이에 특수 문자 삽입:

StringBuilder sb = new StringBuilder("#");
for (char c : input.toCharArray()) {
    sb.append(c).append("#");
}
String modifiedString = sb.toString();

• 입력 문자열에서 짝수 길이의 회문도 쉽게 찾기 위해 모든 문자 사이에 #을 삽입해 새로운 문자열을 만든다.
• 이 과정을 통해 모든 회문은 홀수 길이가 되며, 이후 계산이 더 간단해진다.

2. Manacher's 알고리즘을 사용한 회문 개수 계산:

public static long manachers(String s) {
    int n = s.length();
    int[] A = new int[n]; // 각 중심에서 확장되는 회문의 길이를 저장하는 배열
    int r = 0, p = 0;     // r: 가장 오른쪽까지 뻗은 회문의 끝, p: 그 중심
    long result = 0;      // 총 회문 개수

• n은 변환된 문자열의 길이, A는 각 중심에서 확장되는 회문의 길이를 저장하는 배열이다.
• r과 p는 각각 가장 오른쪽 끝까지 확장한 회문의 끝 위치와 그 중심을 나타낸다.
• result는 최종 회문의 개수를 저장하는 변수다.

3. 회문 길이 대칭성 활용:

if (i <= r) {
    A[i] = Math.min(A[2 * p - i], r - i);
}

• 현재 위치 i가 r 이내에 있으면, A[i] 값을 중심 대칭을 통해 A[2 * p - i]와 r - i 중 작은 값으로 설정한다. 이는 회문의 대칭성을 활용해 이미 계산된 값을 재활용하기 위한 것이다.

4. 회문 확장:

while (i - A[i] - 1 >= 0 && i + A[i] + 1 < n && s.charAt(i - A[i] - 1) == s.charAt(i + A[i] + 1)) {
    A[i]++;
}

• i를 중심으로 좌우로 확장하면서 회문의 길이를 증가시킨다. 이 과정에서 A[i]는 중심 i에서 확장할 수 있는 최대 길이를 저장한다.

5. 가장 오른쪽 회문 업데이트:

if (r < i + A[i]) {
    r = i + A[i];
    p = i;
}

• 현재 중심 i에서 확장한 회문이 r보다 오른쪽으로 뻗어 있다면, r과 p를 업데이트한다. 이를 통해 다음 위치에서 대칭성을 활용할 수 있게 한다.

6. 회문 개수 누적 계산:

result += (A[i] + 1) / 2;

• A[i]의 값이 회문의 길이를 나타내므로, 각 중심에서 발견된 회문 수는 (A[i] + 1) / 2로 계산된다.
• 모든 중심에 대해 회문 수를 누적하여 최종 result에 저장한다.

So...

Manacher's 알고리즘을 활용하여 효율적으로 주어진 문자열 내 부분 문자열 중 회문인 것의 개수를 구할 수 있었다. 이 알고리즘을 사용하지 않고 모든 부분 문자열을 탐색하면 O(n^2)~O(n^3) 복잡도가 될 수 있어 시간 초과가 발생했을 것이다. Manacher's 알고리즘의 대칭성을 활용하여 O(n)으로 해결한 것이 핵심이었다.