Group Anagrams — 정렬 키와 문자 개수 키로 애너그램 묶기

애너그램 그룹화, 어떤 문제인가요?

LeetCode 49번 문제는 이렇게 주어집니다.

문자열 배열 strs가 주어졌을 때, 서로 애너그램인 문자열끼리 그룹으로 묶어 반환하세요. 반환되는 그룹의 순서는 상관없습니다.

애너그램은 같은 문자를 같은 개수만큼 사용하되, 순서만 다른 문자열을 말합니다.

예시는 이렇습니다.

strs = ["eat","tea","tan","ate","nat","bat"]

결과 예시 = [
    ["bat"],
    ["nat","tan"],
    ["ate","eat","tea"]
]

"eat", "tea", "ate"는 모두 a, e, t를 하나씩 가지고 있으므로 같은 그룹입니다. "tan"과 "nat"도 같은 문자 구성을 가지므로 같은 그룹입니다.

제약은 다음과 같습니다.

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i]는 소문자 영문자로만 구성

이 문제의 핵심은 두 문자열을 매번 직접 비교하는 것이 아니라, 애너그램끼리는 같은 키를 갖도록 변환하는 것입니다. 이 글에서는 정렬된 문자열을 키로 쓰는 가장 직관적인 풀이부터, 소문자 26개 개수 배열을 키로 바꾸는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

애너그램은 같은 키를 가져야 합니다

"eat", "tea", "ate"를 각각 정렬해 봅시다.

"eat" -> "aet"
"tea" -> "aet"
"ate" -> "aet"

순서는 달라도 정렬한 결과는 모두 같습니다. 즉 정렬된 문자열 "aet"을 그룹 키로 쓰면 세 문자열을 같은 그룹에 넣을 수 있습니다.

반대로 "tan"과 "bat"는 이렇게 됩니다.

"tan" -> "ant"
"bat" -> "abt"

키가 다르므로 다른 그룹입니다.

이 관점으로 문제를 바꾸면 다음과 같습니다.

각 문자열을 대표 키로 바꾼다
같은 키를 가진 문자열들을 같은 리스트에 모은다

해시맵은 이 구조에 잘 맞습니다.

key -> 같은 애너그램 그룹

Phase 1. 정렬된 문자열을 키로 사용하기

가장 직관적인 방법은 각 문자열의 문자를 정렬해서 키로 쓰는 것입니다.

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val groups = HashMap<String, MutableList<String>>()

    for (str in strs) {
        val key = str.toCharArray()
            .sorted()
            .joinToString("")

        groups.getOrPut(key) { mutableListOf() }.add(str)
    }

    return groups.values.toList()
}

groups는 다음 의미를 가집니다.

정렬된 문자열 -> 원본 문자열 목록

예제 입력을 처리하면 대략 이렇게 쌓입니다.

"eat" -> key "aet" -> ["eat"]
"tea" -> key "aet" -> ["eat", "tea"]
"tan" -> key "ant" -> ["tan"]
"ate" -> key "aet" -> ["eat", "tea", "ate"]
"nat" -> key "ant" -> ["tan", "nat"]
"bat" -> key "abt" -> ["bat"]

마지막에 groups.values만 꺼내면 애너그램 그룹 목록이 됩니다.

[
    ["eat", "tea", "ate"],
    ["tan", "nat"],
    ["bat"]
]

문제는 반환 순서를 요구하지 않으므로 그룹 순서나 그룹 내부 순서가 예시와 달라도 괜찮습니다.

getOrPut은 무엇을 하나요?

Kotlin의 getOrPut은 해시맵에 키가 있으면 기존 값을 가져오고, 없으면 새 값을 넣은 뒤 가져옵니다.

groups.getOrPut(key) { mutableListOf() }.add(str)

위 코드는 다음 흐름을 짧게 쓴 것입니다.

if (key !in groups) {
    groups[key] = mutableListOf()
}

groups[key]!!.add(str)

애너그램 그룹화처럼 "키별 리스트에 원소를 계속 추가하는" 문제에서는 getOrPut을 쓰면 코드가 깔끔해집니다.

정렬 키 풀이의 복잡도

문자열 개수를 n, 문자열 하나의 최대 길이를 k라고 하겠습니다.

각 문자열을 정렬하는 데 O(k log k)가 걸립니다. 이 작업을 n개 문자열에 대해 수행하므로 시간 복잡도는 다음과 같습니다.

O(n * k log k)

공간 복잡도는 해시맵에 모든 문자열을 그룹으로 저장하므로 O(n * k)로 볼 수 있습니다. 정렬 키 문자열도 해시맵 키로 저장됩니다.

이 풀이만으로도 충분히 통과할 수 있습니다. 다만 입력이 소문자 영문자 26개로 제한되어 있으므로, 정렬하지 않고 문자 개수만 세는 방식도 가능합니다.

Phase 2. 문자 개수 배열을 키로 사용하기

애너그램은 각 문자의 등장 횟수가 같습니다.

"eat" -> a:1, e:1, t:1
"tea" -> a:1, e:1, t:1
"ate" -> a:1, e:1, t:1

소문자 영문자만 나오므로 길이 26짜리 배열로 문자 개수를 표현할 수 있습니다.

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val groups = HashMap<String, MutableList<String>>()

    for (str in strs) {
        val counts = IntArray(26)

        for (ch in str) {
            counts[ch - 'a']++
        }

        val key = counts.joinToString("#")
        groups.getOrPut(key) { mutableListOf() }.add(str)
    }

    return groups.values.toList()
}

"eat"의 counts는 이런 의미입니다.

a: 1
b: 0
c: 0
...
e: 1
...
t: 1
...
z: 0

"tea"도 같은 개수 배열을 만듭니다. 그래서 joinToString("#")으로 만든 키도 같습니다.

"eat" -> "1#0#0#0#1#0#...#1#..."
"tea" -> "1#0#0#0#1#0#...#1#..."
"ate" -> "1#0#0#0#1#0#...#1#..."

정렬을 하지 않고 문자열을 한 번만 훑기 때문에, 문자열 하나를 처리하는 비용은 O(k)입니다. 전체 시간 복잡도는 O(n * k)입니다. 길이 26짜리 키를 만드는 비용은 상수에 가깝게 볼 수 있습니다.

왜 IntArray를 그대로 키로 쓰면 안 되나요?

Kotlin/JVM에서 배열은 내용 기준이 아니라 참조 기준으로 비교됩니다. 즉 값이 같은 두 IntArray라도 서로 다른 객체라면 해시맵 키로는 다르게 취급될 수 있습니다.

val a = intArrayOf(1, 0, 1)
val b = intArrayOf(1, 0, 1)

println(a == b) // false

그래서 다음처럼 IntArray를 그대로 키로 쓰면 의도대로 그룹화되지 않습니다.

val groups = HashMap<IntArray, MutableList<String>>() // 피하는 편이 좋음

문자 개수 배열을 키로 쓰고 싶다면 내용 기준으로 비교되는 형태로 바꿔야 합니다.

val key = counts.joinToString("#")

또는 counts.toList()처럼 리스트로 바꿔 키로 사용할 수도 있습니다.

val key = counts.toList()

여기서는 문자열 키가 설명하기 쉽고 디버깅하기도 편해서 joinToString("#")을 사용했습니다. 구분자 #를 넣는 이유는 숫자들을 그냥 이어 붙였을 때 생길 수 있는 모호함을 없애기 위해서입니다.

[1, 11] -> "111"
[11, 1] -> "111"

구분자를 넣으면 두 키가 달라집니다.

[1, 11] -> "1#11"
[11, 1] -> "11#1"

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과 예시	이유
["eat","tea","tan","ate","nat","bat"]	[["eat","tea","ate"],["tan","nat"],["bat"]]	기본 예시
[""]	[[""]]	빈 문자열도 하나의 문자열
["a"]	[["a"]]	원소 하나는 그대로 한 그룹
["",""]	[["",""]]	빈 문자열끼리는 애너그램
["a","b","c"]	[["a"],["b"],["c"]]	모두 다른 문자 구성
["abc","bca","cab","abb"]	[["abc","bca","cab"],["abb"]]	같은 문자 개수끼리 묶임

특히 빈 문자열을 놓치지 않아야 합니다. strs[i].length는 0일 수 있으므로 ""도 입력으로 들어올 수 있습니다. 정렬 키 풀이에서는 빈 문자열의 키가 ""이고, 문자 개수 키 풀이에서는 모든 값이 0인 키가 됩니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
정렬된 문자열을 키로 사용	O(n * k log k)	O(n * k)	가장 직관적이고 구현이 짧음
문자 개수 배열을 문자열 키로 사용	O(n * k)	O(n * k)	소문자 26개 제약을 활용해 정렬 비용 제거

여기서 n은 문자열 개수, k는 문자열 하나의 최대 길이입니다.

실전에서는 정렬 키 풀이가 가장 읽기 쉽고 실수할 여지가 적습니다. 최적화까지 의식한다면 문자 개수 키 풀이가 더 좋은 선택입니다. 다만 Kotlin에서는 IntArray를 해시맵 키로 그대로 쓰지 않는다는 점을 반드시 기억해야 합니다.

마무리

1. 애너그램은 같은 대표 키를 가져야 합니다 — 정렬 결과나 문자 개수 배열이 대표 키가 될 수 있습니다
2. 정렬 키 풀이는 구현이 가장 단순합니다 — 단어를 정렬한 문자열을 해시맵 키로 사용하면 됩니다
3. 문자 개수 키 풀이는 정렬 비용을 줄입니다 — 소문자 영문자 26개 제약을 활용합니다
4. Kotlin에서 IntArray를 그대로 해시맵 키로 쓰면 안 됩니다 — 내용 기준 비교가 아니므로 joinToString이나 toList()로 바꿔야 합니다
5. 반환 순서는 중요하지 않습니다 — 같은 애너그램끼리만 같은 그룹에 있으면 됩니다