Note
문자열 배열에서 서로 애너그램인 것끼리 묶을 때, 정렬된 문자열을 키로 쓰면 같은 그룹을 한 번에 모을 수 있는 원리입니다.
애너그램이란?
두 문자열이 애너그램(anagram) 이라 함은, 한 쪽을 재배열해서 다른 쪽을 만들 수 있다는 뜻입니다.
- 문자 종류와 개수가 같고, 순서만 다름
- 예:
"eat","tea","ate"→ 모두 같은 문자 {a, e, t}를 한 번씩 사용
따라서 같은 문자 multiset(중복 집합) 을 가지면 애너그램입니다.
핵심 아이디어: 정렬 = 대표 키
문자열을 알파벳 순으로 정렬하면:
- 애너그램끼리는 같은 문자열이 됨
"eat"→"aet","tea"→"aet","ate"→"aet"
- 애너그램이 아니면 다른 문자열이 됨
"bat"→"abt"
그래서 정렬된 문자열을 그룹의 대표 키로 쓰면,
같은 키를 가진 문자열끼리 한 그룹으로 묶을 수 있습니다.
알고리즘 설계
- 빈 딕셔너리 준비:
key(정렬된 문자열) → [원본 문자열들] - 각 문자열 s에 대해:
- s를 정렬한 결과를 key로 계산
- key가 이미 있으면 해당 리스트에 s 추가
- 없으면
[s]로 새 리스트 등록
- 딕셔너리의 value 리스트들을 모아서 반환
한 번 순회로 그룹이 나뉘므로 시간 O(n × k log k) (n = 문자열 개수, k = 최대 길이), 공간 O(n × k) 입니다.
예시: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
| 원본 | 정렬 키 |
|---|---|
| ”eat" | "aet" |
| "tea" | "aet" |
| "tan" | "ant" |
| "ate" | "aet" |
| "nat" | "ant" |
| "bat" | "abt” |
딕셔너리:
"aet"→ [“eat”, “tea”, “ate”]"ant"→ [“tan”, “nat”]"abt"→ [“bat”]
반환: [["eat","tea","ate"], ["tan","nat"], ["bat"]] (순서는 무관)
대안: 문자 개수 튜플을 키로
정렬 대신 문자별 등장 횟수를 세어 튜플/문자열로 만들 수도 있습니다.
- 예:
"aet"→ (a:1, e:1, t:1) →(1,0,...,1,...,1,...)같은 형태 - 애너그램이면 이 “카운트 벡터”가 같음
정렬 키 방식이 구현이 간단하고, Python에서는 딕셔너리에 리스트를 value로 두기 좋습니다.
요약
| 항목 | 내용 |
|---|---|
| 애너그램 | 같은 문자 구성, 순서만 다름 |
| 그룹 키 | 문자열을 정렬한 결과 |
| 자료구조 | dict: key = 정렬된 문자열, value = 원본 문자열 리스트 |
| 한 번 순회 | 각 s에 대해 key 계산 후 dict에 추가/생성 |
관련 문제
- LeetCode 49: Group Anagrams - 코드 구조 설명