JavaScript에서 최대 한 글자를 삭제해 문자열을 회문으로 만들 수 있는지 확인하는 방법

문제 소개

문자열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 함수가 해야 할 일은, 문자열에서 최대 한 개의 문자를 삭제했을 때 해당 문자열을 회문(palindrome)으로 만들 수 있는지 확인하고, 가능하면 true, 불가능하면 false를 반환하는 것입니다.

예시

입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str = 'kjlk';

이때 기대하는 출력은 다음과 같습니다.

const output = true;

문자열에서 'l'을 하나 삭제하면 'kjk'만 남게 되는데, 이는 앞에서 읽어도 뒤에서 읽어도 같은 회문이기 때문입니다.

접근 방식: 투 포인터(Two Pointer)

이 문제는 문자열 양 끝에서부터 안쪽으로 이동하는 투 포인터 기법으로 효율적으로 해결할 수 있습니다. 동작 과정은 다음과 같습니다.

왼쪽(left)과 오른쪽(right) 포인터를 문자열의 양 끝에 배치합니다.
두 포인터가 가리키는 문자가 같다면, 두 포인터를 안쪽으로 한 칸씩 이동시킵니다.
두 문자가 서로 다르다면, 왼쪽 문자를 건너뛰었을 때와 오른쪽 문자를 건너뛰었을 때 각각 나머지 구간이 회문인지 확인합니다.
두 경우 모두 회문이 아니라면 한 번의 삭제만으로는 회문을 만들 수 없으므로 false를 반환합니다.

구현 코드

const str = 'kjlk';
const isPalindrome = (str = '', start, end) => {
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        };
        start ++;
        end --;
    };
    return true;
};
const canMakePalindrome = (str = '') => {
    let left = 0, right = str.length - 1;
    while (left < right - 1) {
        if (str[left] !== str[right]) {
            if (isPalindrome(str, left, right - 1)) {
                return true;
            };
            if (isPalindrome(str, left + 1, right)) {
                return true;
            };
            return false;
        } else {
            left ++;
            right --;
        };
    };
    return true;
}
console.log(canMakePalindrome(str));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true

코드 설명 및 시간 복잡도

보조 함수 isPalindrome은 시작 인덱스와 끝 인덱스 사이의 부분 문자열이 회문인지 검사하는 역할을 합니다. 메인 함수 canMakePalindrome은 전체 문자열을 양 끝에서 비교해 가다가 처음으로 불일치가 발생하는 지점에서, 어느 한쪽 문자를 제거한 상황을 시뮬레이션하여 회문 여부를 최종 판단합니다.

모든 비교가 선형 순회로 이루어지므로 시간 복잡도는 O(n)이며, 추가적인 자료 구조를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다. 따라서 긴 문자열에 대해서도 매우 효율적으로 동작합니다.