LeetCode

LeetCode 49 Group Anagrams 풀이: 문자 빈도 해시로 애너그램 그룹화

2026년 9월 18일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 49. Group Anagrams
출처: LeetCode
자체 판단 난이도: Level 2

단어를 구성하는 문자의 종류와 개수가 같으면 순서가 달라도 같은 애너그램 그룹으로 묶을 수 있다. 각 단어의 문자 빈도를 해시 키로 만드는 발상이 필요하지만, 입력이 소문자 영어로 제한되어 구현은 단순하므로 Level 2로 판단했다.

1. 문제 요약

문자열 배열 strs가 주어지면 서로 애너그램인 문자열끼리 하나의 목록으로 묶어 반환한다. 결과 그룹과 그룹 안의 문자열 순서는 자유롭게 반환해도 된다.

애너그램은 문자 순서만 다르고 각 문자의 등장 횟수는 같은 문자열이다. 예를 들어 eat, tea, ate는 모두 a, e, t를 한 번씩 가지므로 같은 그룹이다.

중요한 조건은 다음과 같다.

strs의 길이는 1 이상 10^4 이하이다.
각 문자열의 길이는 0 이상 100 이하이다.
문자열은 소문자 영어로만 구성된다.
빈 문자열도 입력으로 올 수 있다.

문자열마다 다른 문자열을 비교하면 입력이 커질 때 같은 문자 구성을 반복해서 확인하게 된다. 각 문자열을 한 번 처리하면서 같은 특징을 가진 문자열을 해시 맵에 모아야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

문자열 키 생성과 그룹 상태

해시 맵 groups의 키는 알파벳 a부터 z까지의 등장 횟수를 담은 길이 26의 튜플이다. 값은 해당 키를 가진 원본 문자열 목록이다.

각 문자열을 읽을 때 다음 순서로 처리한다.

길이 26인 카운트 배열을 모두 0으로 만든다.
문자열의 각 문자를 순회하며 ord(character) - ord("a") 위치의 개수를 증가시킨다.
리스트를 딕셔너리 키로 사용할 수 있도록 튜플로 변환한다.
같은 튜플을 가진 그룹에 원본 문자열을 추가한다.
딕셔너리의 값들만 모아 반환한다.

문자 빈도 튜플을 그룹 키로 쓰는 이유

애너그램인지 판단할 때 문자의 순서는 중요하지 않고 각 문자의 개수만 중요하다. 그래서 eat, tea, ate는 모두 다음과 같은 동일한 빈도 표현을 만든다.

a: 1, e: 1, t: 1, 나머지 문자: 0

입력이 소문자 영어로 제한되어 있으므로 문자열마다 정렬된 문자열을 만들지 않고 고정된 26칸만 확인하면 된다. 빈 문자열은 카운트가 모두 0인 튜플을 키로 사용하므로 별도의 예외 처리가 필요하지 않다.

리스트는 변경 가능한 객체이므로 딕셔너리 키로 사용할 수 없다. 카운트가 끝난 뒤 불변 객체인 튜플로 바꾸어 키로 사용해야 한다.

시간·공간 복잡도

문자열의 개수를 m, 가장 긴 문자열의 길이를 n이라고 하자. 각 문자를 한 번씩 확인하므로 시간 복잡도는 O(mn)이다. 문자열마다 카운트 배열을 만드는 비용은 26으로 고정되어 O(m)으로 볼 수 있고, 전체 출력과 그룹 저장까지 포함한 공간 복잡도는 원본 문자열을 포함해 O(mn)이다. 반환 결과를 제외한 해시 키와 보조 카운트 배열의 공간은 O(m)이다.

3. 문제 해결 코드 (Python)

groups는 문자 빈도 튜플을 그룹 식별자로 사용한다. defaultdict(list)를 사용하면 처음 등장한 키에 빈 목록을 만드는 조건문 없이 바로 원본 문자열을 추가할 수 있다.

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)

        for word in strs:
            count = [0] * 26

            for character in word:
                index = ord(character) - ord("a")
                count[index] += 1

            groups[tuple(count)].append(word)

        return list(groups.values())

문자열 자체가 아니라 원본 문자열을 값 목록에 넣으므로 입력의 순서와 중복도 보존된다. 예를 들어 같은 단어가 두 번 들어오면 같은 그룹에 두 번 추가된다. tuple(count)는 카운트를 모두 채운 뒤에 만들어야 하며, 카운트 리스트를 그대로 키로 사용하면 Python에서 TypeError가 발생한다.

4. 오답 접근과 반례

구분자 없이 빈도를 문자열로 이어 붙이기

카운트 배열의 숫자를 구분자 없이 이어 붙여 키를 만들면 서로 다른 빈도 배열이 같은 키가 될 수 있다. 예를 들어 a가 1개이고 b가 11개인 경우와 a가 11개이고 b가 1개인 경우 앞의 두 카운트만 이어 붙이면 모두 111이 된다.

"abbbbbbbbbbb"  -> a: 1,  b: 11
"aaaaaaaaaaab"  -> a: 11, b: 1

두 문자열은 애너그램이 아니지만 잘못 만든 키로는 같은 그룹이 될 수 있다. 이 글의 풀이는 튜플의 각 위치를 별도로 유지하므로 이런 충돌이 없다.

매번 문자를 정렬해 키 만들기

sorted(word)를 사용해 정렬된 문자열을 키로 만드는 방식도 정답이 될 수 있다. 그러나 각 문자열 길이가 n일 때 정렬에 O(n log n)이 필요해 전체 시간 복잡도가 O(mn log n)이 된다. 소문자 26종만 사용할 수 있는 이 문제에서는 빈도 카운트가 정렬보다 효율적이다.

복사해 실행할 테스트

아래 검사는 그룹 순서와 그룹 내부 순서가 달라도 같은 결과로 비교하도록 정렬한다.

solver = Solution()
actual = solver.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(group) for group in actual) == sorted([
    ["ate", "eat", "tea"], ["nat", "tan"], ["bat"]
])

5. 공식 예제와 추가 검증

작성한 groupAnagrams 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다. 문제에서 결과 순서를 자유롭게 허용하므로 비교할 때 각 그룹 내부와 그룹 목록을 정렬해 내용만 비교했다.

공식 예제

입력	기대 결과	확인 결과
`["eat","tea","tan","ate","nat","bat"]`	`[["ate","eat","tea"],["nat","tan"],["bat"]]`	통과
`[""]`	`[[""]]`	통과
`["a"]`	`[["a"]]`	통과

추가 검증 1: 중복 문자열

입력: strs = ["ab", "ba", "abc", "cab", "bca", "ab"]
기대 출력: [["ab", "ab", "ba"], ["abc", "bca", "cab"]]
확인 결과: 통과
검증 목적: 같은 문자열의 중복을 누락하지 않고 같은 애너그램 그룹에 추가하는지 확인

추가 검증 2: 길이가 다른 비애너그램

입력: strs = ["a", "aa", "aaa"]
기대 출력: [["a"], ["aa"], ["aaa"]]
확인 결과: 통과
검증 목적: 같은 문자의 종류라도 등장 횟수가 다르면 분리하는지 확인

추가 검증 3: 키 충돌을 만들 수 있는 빈도

입력: strs = ["abbbbbbbbbbb", "aaaaaaaaaaab"]
기대 출력: [["abbbbbbbbbbb"], ["aaaaaaaaaaab"]]
확인 결과: 통과
검증 목적: 문자별 위치를 보존한 튜플 키가 서로 다른 빈도를 구분하는지 확인

6. 다른 풀이 방식 검색 및 비교

Group Anagrams 공식 문제는 애너그램을 같은 목록으로 묶고 결과 순서를 제한하지 않는다.
NeetCode의 Group Anagrams 설명은 정렬 키 방식과 문자 빈도 해시 방식의 차이를 비교한다.

정렬 키 방식은 각 단어를 정렬한 결과를 해시 맵의 키로 사용하므로 이해하기 쉽고 일반적인 문자 집합에도 적용하기 좋다. 반면 문자 빈도 방식은 입력 문자가 소문자 26종이라는 조건을 활용해 정렬을 제거하고 O(mn)에 처리한다.

이 글에서는 고정된 알파벳 범위를 직접 활용하는 빈도 튜플 방식을 선택했다. 튜플은 딕셔너리 키로 안전하게 사용할 수 있고, 입력에 빈 문자열이나 중복 문자열이 있어도 같은 규칙으로 처리할 수 있다.

마무리

Group Anagrams는 단어의 표면적인 문자 순서가 아니라 문자별 등장 횟수를 비교해야 하는 문제다. 소문자 영어 26개의 빈도를 튜플로 만들어 해시 맵에 저장하면 애너그램을 한 그룹으로 묶으면서 각 문자를 한 번씩만 확인할 수 있다. 이 방식은 정렬을 사용하지 않아 O(mn) 시간에 동작하며, 카운트 배열을 튜플로 변환하는 것이 핵심 구현 포인트다.