그룹 애너그램이란?
애너그램(Anagram)은 같은 문자들로 구성되어 있지만 순서가 다른 문자열을 의미합니다. 예를 들어 'eat', 'tea', 'ate'는 모두 같은 글자(e, a, t)로 이루어져 있으므로 서로 애너그램 관계입니다.
이번 문제에서는 주어진 문자열 배열에서 서로 애너그램인 문자열들을 하나의 그룹으로 묶어야 합니다.
문제 예시
입력이 ["eat", "tea", "tan", "ate", "nat", "bat"]라면, 다음과 같이 세 개의 그룹으로 나뉩니다.
- ["ate", "eat", "tea"] — e, a, t로 구성
- ["nat", "tan"] — n, a, t로 구성
- ["bat"] — b, a, t로 구성
해결 접근 방식
핵심 아이디어는 간단합니다. 애너그램끼리는 문자를 정렬하면 반드시 동일한 문자열이 된다는 점을 활용합니다. 이 정렬된 문자열을 딕셔너리(해시맵)의 키(key)로 사용하면 애너그램들을 손쉽게 그룹화할 수 있습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 결과를 저장할 빈 딕셔너리(result)를 생성합니다.
- 문자열 배열의 각 요소에 대해 반복합니다.
- 현재 문자열을 정렬한 뒤 하나의 문자열로 합쳐(join) 키 x를 만듭니다.
- x가 이미 result에 존재하면, 해당 키의 리스트에 현재 문자열을 추가(append)합니다.
- 존재하지 않으면, result[x]를 현재 문자열로 초기화한 새 리스트로 설정합니다.
- 모든 처리가 끝나면 result의 값(values)들을 리스트로 반환합니다.
파이썬 구현 코드
아래는 위 알고리즘을 실제로 구현한 파이썬 코드입니다.
class Solution:
def groupAnagrams(self, strs):
result = {}
for i in strs:
x = "".join(sorted(i))
if x in result:
result[x].append(i)
else:
result[x] = [i]
return list(result.values())
ob1 = Solution()
print(ob1.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
실행 결과
입력
["eat", "tea", "tan", "ate", "nat", "bat"]
출력
[["ate", "eat", "tea"], ["nat", "tan"], ["bat"]]
복잡도 분석
각 문자열을 정렬할 때 O(k log k)의 시간이 걸린다면(여기서 k는 문자열의 평균 길이), 전체 시간 복잡도는 O(n · k log k)입니다(n은 문자열 개수). 공간 복잡도는 모든 문자열을 저장해야 하므로 O(n · k)입니다.
이처럼 정렬 결과를 해시 키로 활용하는 방법은 그룹 애너그램 문제를 해결하는 가장 직관적이고 효율적인 접근법 중 하나입니다.