JavaScript로 문자열 재배열 시 회문 생성 가능 여부 확인하기

문제 개요

문자열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수의 역할은 문자열의 문자들을 임의로 재배열했을 때 회문(palindrome)이 되는 경우가 존재하는지 판별하는 것입니다. 회문을 만들 수 있다면 true, 그렇지 않다면 false를 반환하면 됩니다.

예를 들어, 입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str = 'amadm';

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

const output = true;

그 이유는 문자열을 재배열하면 'madam'이라는 회문을 만들 수 있기 때문입니다.

접근 방식

회문의 핵심 성질을 먼저 이해하면 문제가 쉬워집니다. 회문에서는 모든 문자가 짝수 번 등장해야 하며, 문자열 길이가 홀수인 경우에 한해 최대 하나의 문자만 홀수 번 등장할 수 있습니다.

따라서 해시(hash) 객체를 사용해 홀수 번 등장한 문자만 추적하면 효율적으로 판별할 수 있습니다. 공백 문자는 회문 판정에서 제외하도록 처리했습니다.

예제 코드

구현 코드는 다음과 같습니다.

const str = 'amadm';
const canFormPalindrome = (str = '') => {
    const hash = {};
    let count = 0;
    for (let i = 0; i < str.length; i++) {
        let c = str[i];
        if(c === ' '){
            continue;
        };
        if(hash[c]){
            delete hash[c];
        }else{
            hash[c] = true;
        };
        count++;
    };
    if(count % 2 === 0){
        return Object.keys(hash).length === 0;
    }else{
        return Object.keys(hash).length === 1;
    };
};
console.log(canFormPalindrome(str));

코드 동작 원리

이 알고리즘은 다음과 같은 방식으로 작동합니다.

먼저 각 문자를 순회하면서 해시 객체에 해당 문자가 이미 존재하면 삭제하고, 존재하지 않으면 추가합니다. 이 과정이 끝나면 해시 객체에는 홀수 번 등장한 문자만 남게 됩니다. 동시에 유효 문자(공백 제외)의 총 개수를 세어 둡니다.

마지막으로 전체 문자 수가 짝수라면 해시 객체가 비어 있어야(모든 문자가 짝수 번 등장) 회문이 가능하고, 홀수라면 정확히 하나의 문자만 남아 있어야 합니다.

출력 결과

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

true

이 알고리즘의 시간 복잡도는 O(n)으로, 문자열을 한 번만 순회하면 되므로 매우 효율적입니다.