JavaScript 문자열 아나그램(Anagram)이란? 개념과 판별 방법

아나그램(Anagram)이란?

두 문자열이 서로 아나그램 관계에 있다는 것은, 첫 번째 문자열의 글자들을 재배열하거나 순서를 섞어 두 번째 문자열과 완전히 동일한 문자열을 만들 수 있다는 의미입니다.

예를 들어 다음 두 단어를 살펴보겠습니다.

'something'과 'emosghtin'은 같은 글자들로 이루어져 있으므로 서로 아나그램입니다.

이번 글에서는 두 개의 문자열 str1과 str2를 입력받아, 두 문자열이 서로 아나그램인 경우 true, 그렇지 않은 경우 false를 반환하는 JavaScript 함수를 작성해 보겠습니다.

접근 방식

가장 효율적인 방법은 문자 빈도수(Frequency Count)를 활용하는 것입니다. 각 문자열에서 각 문자가 몇 번 등장하는지 객체에 저장한 뒤, 두 객체를 비교하여 모든 문자의 개수가 일치하는지 확인합니다.

판별 과정은 다음과 같습니다.

1. 두 문자열의 길이가 다르면 즉시 false를 반환합니다.
2. 첫 번째 문자열을 순회하며 각 문자의 등장 횟수를 객체 obj1에 기록합니다.
3. 두 번째 문자열도 동일하게 객체 obj2에 기록합니다.
4. obj1의 모든 키가 obj2에 존재하고, 값(개수)까지 일치하는지 확인합니다.

예제 코드

const str1 = "something";
const str2 = "emosghtin";

const validAnagram = (str1 = '', str2 = '') => {
    // 길이가 다르면 아나그램일 수 없음
    if (str1.length !== str2.length) {
        return false;
    }

    let obj1 = {};
    let obj2 = {};

    // str1의 문자 빈도수 계산
    for (let char of str1) {
        obj1[char] = (obj1[char] || 0) + 1;
    }

    // str2의 문자 빈도수 계산
    for (let char of str2) {
        obj2[char] = (obj2[char] || 0) + 1;
    }

    // 두 객체의 문자 개수 비교
    for (let val in obj1) {
        if (!(val in obj2) || (obj2[val] !== obj1[val])) {
            return false;
        }
    }

    return true;
};

console.log(validAnagram(str1, str2));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

true

코드 설명

(obj1[char] || 0) + 1 구문은 해당 문자가 처음 등장했을 때 undefined가 되는 것을 방지하기 위해 사용됩니다. 문자가 이미 존재하면 기존 값에 1을 더하고, 없다면 0에서 시작해 1을 더합니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 문자열의 길이에 비례하여 선형적으로 처리되므로 매우 효율적입니다. 공간 복잡도 역시 문자 종류에 따라 달라지지만 최대 O(n)입니다.

마무리

문자 빈도수를 비교하는 방법 외에도, 두 문자열을 각각 정렬한 후(split('').sort().join('')) 일치 여부를 확인하는 방법도 있습니다. 다만 정렬 방식은 시간 복잡도가 O(n log n)이므로, 긴 문자열을 다룰 때는 위와 같은 빈도수 비교 방식이 더 유리합니다.