Dlog

애너그램(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) 시간 복잡도를 유지할 수 있다.

빈도 카운터 (Frequency Counter)란?

빈도 카운터는 배열이나 문자열에서 각 요소나 문자의 빈도(몇 번 나오는지)를 세는 방법이다.

알고리즘에서 빈도 카운터 패턴(Frequency Counter Pattern)은 객체(Object)나 Set과 같은 자료구조를 사용하여 배열이나 문자열 내의 값들의 빈도(즉, 특정 값이 몇 번 등장하는지)를 수집하고 이를 비교하는 방법이다. 이 패턴은 중첩된 루프나 O(N^2)와 같은 비효율적인 연산을 피하는 데 매우 유용하다

빈도 카운터는 보통 객체를 사용

자바스크립트에서 보통 객체를 사용하여 이러한 빈도 카운터를 만든다. 객체는 key-value 쌍으로 데이터를 저장하므로, 특정 요소를 key로, 그 요소의 빈도를 value로 저장할 수 있다.

예를 들어, 배열 [1, 2, 2, 3, 3, 3]의 빈도를 계산해봅시다

let frequencyCounter = {};
let arr = [1, 2, 2, 3, 3, 3];

for (let num of arr) {
    frequencyCounter[num] = (frequencyCounter[num] || 0) + 1;
}

이 코드는 frequencyCounter 객체를 다음과 같이 만든다

{
    1: 1,  // 1은 1번 등장
    2: 2,  // 2는 2번 등장
    3: 3   // 3은 3번 등장
}

빈도 카운터 패턴 예시 문제 

• 함수 이름: same
• 목표: 첫 번째 배열의 각 값의 제곱이 두 번째 배열에 동일한 빈도로 존재하는지 확인합니다.
• 입력: 두 개의 배열 (arr1, arr2)
• 출력: 첫 번째 배열의 모든 값의 제곱이 두 번째 배열에 같은 빈도로 존재하면 true, 그렇지 않으면 false를 반환.

same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)

1. A Naive Solution

function same(arr1, arr2) {
    if (arr1.length !== arr2.length) {
        return false;
    }
    for (let i = 0; i < arr1.length; i++) {
        let correctIndex = arr2.indexOf(arr1[i] ** 2);
        if (correctIndex === -1) {
            return false;
        }
        arr2.splice(correctIndex, 1);
    }
    return true;
}

Time Complexity: N^2

이 코드는 첫 번째 배열의 각 요소를 기준으로 다시 배열 전체를 탐색하여 해당 요소가 몇 번 등장했는지 확인한다. 이 과정은 매우 비효율적이며, 배열의 길이가 n일 때, 시간 복잡도가 O(n^2)이 된다

2. refactored

빈도 카운터: 두 배열의 각 요소의 빈도를 계산하는 두 개의 빈도 카운터(객체)를 만든다.

function same(arr1, arr2) {
    if (arr1.length !== arr2.length) {
        return false;
    }
    let frequencyCounter1 = {};
    let frequencyCounter2 = {};

    for (let val of arr1) {
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
    }

    for (let val of arr2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
    }

    for (let key in frequencyCounter1) {
        if (!(key ** 2 in frequencyCounter2)) {
            return false;
        }
        if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
            return false;
        }
    }

    return true;
}

Time Complexity: O(n)

반면, 빈도 카운터를 사용한 방법은 배열을 한 번만 순회하면서 각 요소의 빈도를 계산하므로 시간 복잡도는 O(n)이 된다

따라서 각각의 두 개의 루프가 두개의 중첩된 개별 루프보다 훨씬 낫다

결론

빈도 카운터 패턴은 배열이나 문자열에서 각 요소의 빈도를 효율적으로 계산하고 이를 활용해 다양한 문제를 해결하는 데 유용한 알고리즘 패턴이다. 중첩된 루프를 사용하여 비효율적으로 문제를 해결하기보다는, 빈도 카운터를 사용하여 시간 복잡도를 크게 줄일 수 있다. 이 패턴을 잘 이해하고 활용하면, 복잡한 문제도 효과적으로 해결할 수 있다.

Big O란?

프로그래밍에서 알고리즘의 효율성을 측정하기 위해 Big O 표기법을 사용한다. 이는 알고리즘이 처리하는 데이터의 크기가 커질수록, 그 알고리즘이 얼마나 많은 시간과 메모리를 사용하는지 나타내는 지표이다.

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 주어진 입력 크기 n에 대해 작업을 수행하는 데 걸리는 시간을 나타낸다.

공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 주어진 입력 크기 n에 대해 작업을 수행하는 데 필요한 메모리 공간을 나타낸다. 이 역시 입력 크기가 커질수록 얼마나 많은 메모리를 사용하는지를 보여준

Big O 복잡도

왜 Big O가 중요한가?

Big O는 코드를 작성할 때 성능을 미리 예측하고 최적화할 수  할 수 있도록 도와준다. 코드가 작은 데이터에서는 빠르게 실행되지만, 데이터가 많아지면 성능이 급격히 떨어질 수도 있다. 이때 Big O를 알면 어떤 코드가 더 효율적인지 쉽게 알 수 있다(성능 최적화).