[알고리즘] 빈도수 카운터 - Anagram

애너그램(Anagram)이란?

하나의 문자열의 문자들을 섞었을 때 다른 단어가 나오는 것을 의미한다.

 

문제 설명: 

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램(anagram)인지 확인하는 함수를 작성하세요. 애너그램이란 어떤 단어나 문장의 문자를 재배열하여 다른 단어나 문장을 만드는 것을 말한다. 예를 들어, cinema는 iceman의 애너그램이다. 함수는 두 문자열이 애너그램이면 true, 그렇지 않으면 false를 반환해야 한다.

validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram('rat', 'car') // false
validAnagram('awesome', 'awesom') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

 

1: 빈도 카운터(Frequency Counter) 방식

function validAnagram(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }
    const Counter1 = {};
    const Counter2 = {};

    for (let char of str1) {
        Counter1[char] = (Counter1[char] || 0) + 1;
    }
    for (let char of str2) {
        Counter2[char] = (Counter2[char] || 0) + 1;
    }
    for (let key in Counter1) {
        if (!(key in Counter2)) {
            return false;
        }
        if (Counter1[key] !== Counter2[key]) {
            return false;
        }
    }

    return true;
}

이 방법은 각각의 문자열에 대해 문자 빈도를 계산한 후, 두 문자열의 문자 빈도를 비교하는 것이다. 두 문자열의 모든 문자가 동일한 빈도를 가지면 이 두 문자열은 애너그램

 

2: 최적화된 빈도 카운터

function validAnagram(first, second) {
    if (first.length !== second.length) {
        return false;
    }

    const lookup = {};

    for (let i = 0; i < first.length; i++) {
        let letter = first[i];
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
    }

    for (let i = 0; i < second.length; i++) {
        let letter = second[i];
        if (!lookup[letter]) {
            return false;
        } else {
            lookup[letter] -= 1;
        }
    }

    return true;
}

두 개의 별도 객체를 만드는 대신, 하나의 객체를 사용하여 두 번째 문자열을 순회하면서 빈도를 감소 시킨다. 

빈도가 충분하지 않거나, 해당 문자가 존재하지 않으면 false를 반환하도록 설계

 

• lookup[letter]가 0이 된 경우, 0도 false로 평가된
• !0는 true

 

 

이러한 방법을 통해 O(n) 시간 복잡도를 유지할 수 있다.