자바스크립트로 최대 한 글자 삭제 후 회문 여부 판별하기

문제 설명

문자열 str을 첫 번째이자 유일한 인수로 받아 처리하는 자바스크립트 함수를 작성해야 합니다.

이 함수는 문자열에서 최대 한 글자까지 삭제할 수 있으며, 그 결과가 회문(팰린드롬), 즉 앞에서 읽으나 뒤에서 읽으나 동일한 문자열이 될 수 있는지 판별해야 합니다.

예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력:

const str = 'dr.awkward';

출력:

const output = true;

출력 설명:

문자열에서 마침표('.')를 삭제하면 'drawkward'가 되며, 이 문자열은 거꾸로 읽어도 동일하기 때문에 회문입니다.

풀이 코드

다음은 투 포인터(two-pointer) 기법을 활용해 이 문제를 해결한 코드입니다 −

const str = 'dr.awkward';
const validPalindrome = (str = '') => {
    const valid = (left, right) => {
         for (let i = left; i <= Math.floor((left + right) / 2); i++) {
            if (str[i] !== str[right - (i - left)]) {
              return false
            }
        }
        return true
    }
    for (let i = 0; i <= Math.floor(str.length / 2); i++) {
        const right = str.length - 1 - i
        if (str[i] !== str[right]) {
            return valid(i, right - 1) || valid(i + 1, right)
        }
    }
    return true
}
console.log(validPalindrome(str));

코드 동작 원리

이 알고리즘은 문자열의 양쪽 끝에서부터 중앙으로 이동하며 두 문자를 비교하는 방식으로 작동합니다. 먼저 일반적인 회문 검사를 수행하고, 일치하지 않는 문자를 발견하면 두 가지 경우를 시도합니다. 왼쪽 문자를 건너뛰는 경우와 오른쪽 문자를 건너뛰는 경우입니다. 두 경우 중 하나라도 회문이라면, 최대 한 글자의 삭제만으로 회문을 만들 수 있다는 뜻입니다. 모든 비교가 통과되면 별도의 삭제 없이도 이미 회문이므로 true를 반환합니다.

실행 결과

true