회문 수열이란?
회문(팰린드롬) 수열은 앞에서 읽으나 뒤에서 읽으나 완전히 동일한 문자열 시퀀스를 의미합니다. 예를 들어 'aba', 'madam', 'did'는 모두 유효한 회문입니다.
이번 글에서는 문자열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해 보겠습니다. 입력 문자열은 'a', 'b', 'c', 'd' 네 가지 문자로만 구성된다고 보장되며, 함수는 해당 문자열에 등장하는 모든 연속 또는 비연속 회문 부분 수열의 개수를 세어 반환해야 합니다.
문제 예시
입력 문자열이 다음과 같다고 가정해 보겠습니다.
const str = 'bccb';
이 경우 기대되는 출력은 다음과 같습니다.
const output = 6;
그 이유는 이 문자열에서 만들 수 있는 회문이 총 6개이기 때문입니다.
- 'b'
- 'c'
- 'bb'
- 'cc'
- 'bcb'
- 'bccb'
접근 방식: 동적 계획법(DP)
이 문제는 구간별 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- dp[i][j]: 인덱스 i부터 j까지의 부분 문자열에서 만들 수 있는 회문 부분 수열의 개수
- 길이가 1인 구간은 자기 자신 하나만 회문이므로 값이 1
- 길이가 2인 구간은 각 문자 하나씩 두 개의 회문을 가지므로 값이 2
- 양 끝 문자(str[i]와 str[j])가 같은지 여부에 따라 점화식이 달라집니다.
양 끝 문자가 같을 때는 내부 구간에서 같은 문자가 또 등장하는 위치를 찾아 중복을 제거하거나 추가해야 하며, 결과값이 커지는 것을 방지하기 위해 1,000,000,007로 나눈 나머지를 저장합니다.
구현 코드
const str = 'bccb';
const countPalindromes = (str = '') => {
let base = 1000000007;
const dp = Array(str.length).fill([]);
for (let l = 1; l <= str.length; l ++) {
for (let i = 0; i + l - 1 < str.length; i ++) {
let j = i + l - 1;
// 길이가 1인 구간: 자기 자신만 회문
if (l === 1) {
dp[i][j] = 1;
continue;
}
// 길이가 2인 구간: 각 문자 하나씩 두 개의 회문
if (l === 2) {
dp[i][j] = 2;
continue;
}
if (str[i] === str[j]) {
let left = i + 1, right = j - 1;
while (left <= right && str[left] != str[i]) {
left ++;
}
while (left <= right && str[right] != str[i]) {
right --;
}
if (left > right) {
// 내부에 같은 문자가 없는 경우
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
}
else if (left === right) {
// 내부에 같은 문자가 정확히 하나 있는 경우
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
// 내부에 같은 문자가 둘 이상 있는 경우 (중복 제거)
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
}
} else {
// 양 끝 문자가 다른 경우: 포함-배제 원리 적용
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
// 오버플로 방지를 위한 모듈러 연산
dp[i][j] = dp[i][j] < 0? dp[i][j] + base : dp[i][j] % base;
}
}
return dp[0][str.length - 1];
};
console.log(countPalindromes(str));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
6
정리
이 알고리즘은 구간의 길이를 1부터 문자열 전체 길이까지 순차적으로 확장해 가며 각 구간의 회문 부분 수열 개수를 누적 계산합니다. 양 끝 문자가 같은 경우에는 내부에 동일한 문자가 존재하는 위치에 따라 세 가지 경우로 나누어 처리하고, 서로 다른 경우에는 포함-배제 원리를 활용해 중복을 제거합니다. 최종적으로 시간 복잡도는 O(n²) 수준으로, 무작정 모든 부분 수열을 생성하는 브루트포스 방식보다 훨씬 효율적으로 문제를 해결할 수 있습니다.