문자열 하나와 시작 인덱스(start)부터 끝 인덱스(end)까지의 범위가 주어졌을 때, 해당 범위 안에 존재하는 회문(팰린드롬) 부분 문자열의 개수를 계산하는 문제입니다. 회문 문자열이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 뜻하며, 'nitin', 'aba' 등이 대표적인 예입니다.
예시
입력 - InputString = "cccaabbbdee", start = 2, end = 6
출력 - 인덱스 범위 내 회문 부분 문자열 개수: 7
설명 - 문자열과 범위가 주어지면 start 포인터인 2('c')부터 6('b')까지 순회하므로 부분 문자열은 'caabb'가 됩니다. 이 범위에서 회문 부분 문자열은 'c', 'a', 'a', 'b', 'b', 'aa', 'bb'로 총 7개입니다.
입력 - InputString = "lioaabbbdee", start = 0, end = 2
출력 - 인덱스 범위 내 회문 부분 문자열 개수: 3
설명 - start 포인터인 0('l')부터 2('o')까지 순회하므로 부분 문자열은 'lio'가 됩니다. 이 범위에서 회문 부분 문자열은 'l', 'i', 'o'로 총 3개입니다.
프로그램에서 사용된 접근 방식
- 임의 크기의 문자열과 start 변수부터 end 변수까지의 범위를 선언합니다.
- 데이터를 palindrome_index(arr, InputString) 함수에 전달하여 후속 처리를 진행합니다.
- 함수 내부에서 문자열 길이와 같은 크기의 2차원 배열 check를 추가로 선언합니다.
- i를 0부터 배열 길이까지 반복하는 FOR 루프를 시작합니다.
- 루프 내부에서 j를 0부터 배열 길이까지 반복하는 또 다른 FOR 루프를 시작합니다.
- 루프 내부에서 check[i][j] = 0과 arr[i][j] = 0으로 초기화하여 모든 값을 0으로 만듭니다.
- i를 length - 1부터 0보다 크거나 같을 때까지 감소시키는 FOR 루프를 시작합니다.
- 루프 내부에서 check[i][i]와 arr[i][i]를 1로 설정한 뒤, j를 i + 1부터 배열 길이까지 반복하는 또 다른 FOR 루프를 시작합니다.
- 루프 내부에서 s의 i번째 문자와 j번째 문자가 서로 같고, (i + 1 > j - 1)이거나 check[i + 1][j - 1]이 0이 아니라면 check[i][j]를 1로, 그렇지 않으면 0으로 설정합니다. 이어서 arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j] 공식으로 누적 개수를 갱신합니다.
- 마지막으로 start와 end를 인덱스로 하여 2차원 배열 arr[start][end]의 값을 출력합니다.
이 방식은 동적 프로그래밍(DP)에 기반합니다. check 테이블은 s[i..j]가 회문인지 여부를 저장하고, arr 테이블은 포함-배제 원리를 이용해 각 구간별 회문 부분 문자열의 누적 개수를 저장합니다. 덕분에 사전 계산 한 번으로 임의의 범위 질의를 O(1) 시간에 답할 수 있습니다.
예제 코드
import java.io.*;
class testqwe {
static void palindrome_index(int arr[][], String s) {
int length = s.length();
int[][] check = new int[length + 1][length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= length; j++) {
check[i][j] = 0;
arr[i][j] = 0;
}
}
for (int i = length - 1; i >= 0; i--) {
check[i][i] = arr[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
check[i][j] =1;
} else {
check[i][j] =0;
}
arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
}
}
}
public static void main(String args[]) {
String InputString = "cccaabbbdee";
int[][] arr;
arr = new int[50][50];
palindrome_index(arr, InputString);
int start = 2;
int end = 6;
System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
}
}참고로 위 예제 코드는 Java로 작성되었지만, 알고리즘 로직 자체는 C++, Python 등 다른 언어로도 동일하게 구현할 수 있습니다.
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력
Count of Palindromic substrings in an Index range 7