242. Valid Anagram

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

문자열 s 와 t가 주어졌을 때, t가 s의 애너그램이면 true, 아니면 false를 반환하는 문제.

풀이 1

아이디어

s에서 각 문자가 몇번 등장하는지 세어준다. (charCount) t에서 문자의 개수를 세어주면서 charCount의 값을 감소시킨다. 문자의 개수가 부족하거나 남는다면 애너그램이 아니다.

코드

function isAnagram(s: string, t: string): boolean {
    const charCount: Record < string, number > = {};
    for (const char of s) {
        charCount[char] = (charCount[char] ?? 0) + 1;
    }

    for (const char of t) {
        if (charCount[char] === undefined || charCount[char] === 0) {
            return false;
        }
        charCount[char]--;
    }

    return Object.values(charCount).every((count) => count === 0);
}

시간 / 공간 복잡도

시간 복잡도: O(n + n + k) => O(n) (n: s와 t의 길이, k: 두 문자열에 등장하는 고유 문자 수)
공간 복잡도: 문자 등장 횟수를 세어주는 charCount에 필요한 공간이므로 O(n)