242. Valid Anagram (LeetCode)

https://leetcode.com/problems/valid-anagram/description/

1. 문제의 본질 파악

아나그램(Anagram)은 단어의 알파벳 순서를 바꿔서 다른 단어를 만드는 것입니다. 즉, "순서는 상관없이 구성하는 각 알파벳의 종류와 개수가 완전히 동일한가?"를 묻는 문제입니다.

두 문자열을 정렬해서 비교하는 방법[O(N log N)]도 있지만, 해시맵(Hash Map)을 활용하면 단 한 번의 카운팅[O(N)]으로 훨씬 빠르게 해결할 수 있습니다.

2. 놓치기 쉬운 엣지 케이스: 얼리 리턴 (Early Return)

문자열을 비교하기 전 가장 먼저 확인해야 할 것은 길이입니다.

두 문자열 s와 t의 길이가 다르다면 알파벳 개수를 셀 필요도 없이 절대로 아나그램이 될 수 없습니다. 코드 극초반에 아래 구문을 넣어 불필요한 해시맵 연산을 원천 차단했습니다.

if (s.length !== t.length) return false;

3. 해시맵 카운트 & 차감 방식

1) 첫 번째 문자열(s) 카운팅

문자열 s를 순회하며 각 문자의 출현 횟수를 해시맵에 기록합니다.

(예: { 'a': 3, 'n': 1, 'g': 1, ... })

2) 두 번째 문자열(t) 차감 및 검증

문자열 t를 순회하며 해당 문자가 해시맵에 존재하는지, 남아있는 수량(0보다 큰지)이 있는지 확인합니다.

• 존재하면 수량을 1 빼서 갱신합니다.
• 만약 해시맵에 없는 문자가 나오거나 이미 수량이 0인 문자가 나오면 아나그램이 아니므로 즉시 false를 반환합니다.

3) 최종 반환

중간에 실패 없이 t 순회를 마쳤다면 두 문자열의 구성 요소가 완전히 일치한다는 의미이므로 true를 반환합니다.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const map = new Map();
    for (const c of s) {
        map.set(c, (map.get(c) ?? 0) + 1)
    }
    
    for (const c of t) {
        if (map.has(c) && map.get(c) > 0) {
            map.set(c, map.get(c) - 1)
        } else {
            return false;
        }
    }

    return true;
};

4. 복잡도 분석

• 시간 복잡도: O(N)
• 문자열 s 순회 O(N) + 문자열 t 순회 O(N) = 최종 O(N) (여기서 N은 문자열의 길이)
• 공간 복잡도: O(1)
• 해시맵에 저장되는 키의 개수는 알파벳 소문자 기준 최대 26개로 제한되므로, 입력 크기 N과 무관하게 상수의 메모리 공간 O(1)을 사용합니다.