Group Anagrams

Q: 애너그램 그룹화의 시간 복잡도는 얼마인가요?

정렬된 문자를 키로 사용하는 해시 맵에서는 최대 k 개의 문자를 가진 n 개의 단어에 대해 키를 만드는 데 O(n · k log k) 가 걸리고, 맵 작업에는 O(n · k) 가 걸립니다. 이 버전은 출력 순서를 정하기 위해 단어도 정렬하므로 O(n · k · log n) 가 추가됩니다. 키와 그룹에 필요한 공간은 O(n · k) 입니다.

Q: 각 단어를 정렬하는 것보다 문자 개수 키를 사용하는 것이 더 빠를까요?

카운트 키는 26개의 문자 개수를 1#0#2#… 와 같은 텍스트로 나열한 것으로, O(k log k) 대신 O(k) 의 시간이 걸리므로 긴 단어에서 더 유리합니다. 길이가 최대 8자인 단어에서는 정렬도 그만큼 빠르며, 출력의 알파벳순 정렬에는 어느 키보다도 더 많은 비용이 듭니다. 두 단어의 문자 개수가 같을 때, 그리고 그때에만 정렬된 문자가 같으므로 두 키 모두 올바릅니다.

Q: 문자 코드의 합을 키로 사용하지 않는 이유는 무엇인가요?

서로 다른 글자들이 같은 합계를 만들 수 있습니다. a + d는 b + c와 같으므로 ad 와 bc 는 같은 그룹에 속하게 됩니다. 애너그램끼리는 같은 키를 갖고 그 외의 모든 경우에는 달라야 하며, 글자를 정렬하거나 각 글자의 개수를 모두 세면 이를 보장할 수 있습니다. 글자마다 소수 하나씩 곱하는 방법도 정확하지만, z에 101을 사용하면 z가 열 개 있는 단어는 이미 64비트 정수의 범위를 넘습니다.

보통해싱 정렬

+10

단어 목록 strs가 주어집니다. 두 단어는 한 단어의 글자 순서를 바꾼 것이 다른 단어일 때 애너그램입니다. 즉, 같은 글자가 같은 횟수만큼 사용됩니다. 모든 단어를 애너그램끼리 그룹으로 묶고, 그룹마다 문자열 하나를 반환하세요. 각 문자열에는 그룹의 단어를 알파벳순으로 정렬하고 단일 공백으로 구분해 담습니다. 그룹은 첫 번째 단어를 기준으로 알파벳순으로 정렬하세요.

두 번 나타나는 단어는 해당 그룹에 두 번 포함하고, 애너그램이 없는 단어는 하나만 있는 그룹을 이룹니다. 알파벳순은 사전식 순서를 뜻합니다. aab는 ab보다 앞에 오고, ab는 abc보다 앞에 옵니다.

함수

groupAnagrams(strs: string-array) → string-array

strsstring-array: 그룹화할 단어, 소문자만 사용
반환값string-array: 그룹당 하나의 문자열: 단어를 정렬한 다음 공백으로 연결하고, 각 그룹의 첫 번째 단어를 기준으로 그룹을 정렬합니다

제약 조건

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
모든 단어는 소문자 영어 문자만 포함합니다.

예제

입력: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
출력: ["apple", "enlist listen silent", "notes onset stone tones"]
설명: enlist, listen, silent는 각각 e, i, l, n, s, t를 한 번씩 사용합니다. notes, onset, stone, tones는 e, n, o, s, t를 공유하며, apple은 어느 것과도 일치하지 않습니다. 첫 번째 단어를 기준으로 그룹을 나열하면 apple, enlist, notes 순입니다.

입력: strs = ["race", "arc", "care", "car", "acre"]
출력: ["acre care race", "arc car"]
설명: acre, care와 race는 a, c, e, r을 공유합니다. arc와 car에는 e가 없으므로 서로 별도의 그룹을 이룹니다. 두 번째 글자에서 c가 r보다 앞서므로 acre는 arc보다 앞에 옵니다.

입력: strs = ["b", "a", "b"]
출력: ["a", "b b"]
설명: b의 두 복사본은 서로 애너그램이며, 둘 다 그룹에 남습니다. a는 짝이 없으며 먼저 옵니다.

제출 시 숨은 테스트 +15개

후속 질문

단어가 26개의 소문자 대신 모든 유니코드 문자를 포함할 수 있다고 가정해 보세요. 두 키 중 정렬된 문자와 문자 개수 중 어느 것이 여전히 작동하며, 그 키를 어떻게 바꾸시겠어요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 단어를 다른 모든 단어와 비교하는 방법도 작동하지만, 각 쌍을 비교하는 데 온전히 한 번의 비교가 필요합니다. 이 문제를 해결하는 핵심은 표준 키입니다. 이는 단어 하나만으로 계산하며 해당 단어의 모든 애너그램에서 동일하고 다른 모든 단어에서는 다른 값입니다. 단어의 글자를 정렬한 순서가 바로 그런 키이며, 키에서 그룹으로 연결하는 해시 맵을 사용하면 한 번의 순회만으로 그룹화할 수 있습니다. 그룹화하기 전에 단어를 정렬하면 원하는 순서도 자연스럽게 얻을 수 있습니다.

각 단어를 모든 그룹과 비교합니다

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

애너그램 관계는 추이적입니다. stone이 notes와 일치하고 notes가 tones와 일치하면, stone은 tones와도 일치합니다. 따라서 새 단어는 그룹의 모든 구성원과 일일이 비교할 필요가 없습니다. 그룹의 첫 번째 단어와 비교하면 그 그룹에 속하는지 결정할 수 있습니다.

두 단어를 비교하려면 글자 수를 세면 됩니다. 두 단어의 길이가 같고 모든 글자가 한쪽에 다른 쪽과 같은 횟수로 나타나면 애너그램입니다. 첫 번째 단어의 각 글자마다 1을 더하고 두 번째 단어의 각 글자마다 1을 뺀 다음, 26개의 카운터가 모두 0이 되는지 확인하세요.

먼저 입력을 정렬하면 순서는 저절로 맞춰집니다. 단어는 알파벳순으로 들어오고 각 단어는 해당 그룹의 끝에 추가되므로 모든 그룹이 정렬된 상태를 유지합니다. 각 그룹은 알파벳순으로 가장 앞선 단어가 들어올 때 만들어지므로 그룹도 첫 번째 단어를 기준으로 이미 정렬되어 있습니다.

비용은 전체 탐색에 있습니다. 어떤 두 단어도 애너그램이 아니라면 각 단어를 그보다 앞선 모든 그룹과 비교합니다. 단어가 4000개면 약 4000 × 3999 / 2 ≈ 8 × 10^6번 비교하게 되며, 비교마다 최대 8개의 글자와 26개의 카운터를 확인합니다. 가장 큰 테스트에서는 Python, Lua, R로 처리하기에 너무 느립니다. 작업량이 목록의 제곱에 비례해 늘어나므로 단어가 10^5개라면 어떤 언어로도 감당하기 어렵습니다.

알고리즘

단어를 알파벳순으로 정렬합니다.
각각 단어 목록인 그룹 목록을 유지합니다.
각 단어에 대해, 첫 번째 단어의 문자 개수가 같은 그룹을 찾아 단어를 추가합니다.
일치하는 그룹이 없으면 이 단어만 포함하는 새 그룹을 시작합니다.
각 그룹의 단어를 공백 하나로 연결하고, 그룹을 만든 순서대로 반환합니다.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

정렬된 문자를 기준으로 해시 맵에서 그룹화하기

핵심 아이디어

단어가 어떤 그룹에 속하는지 묻는 대신, 단어 자체에서 그룹 이름을 계산하세요. 단어의 글자를 정렬하면 모든 애너그램이 같은 문자열이 됩니다. listen, silent, enlist는 모두 eilnst가 되고, stone은 enost가 됩니다. 두 단어의 정렬된 형태가 같다는 것은 같은 글자가 같은 횟수만큼 들어 있다는 뜻이며, 이것이 애너그램의 정의입니다. 따라서 정렬된 형태가 그룹의 표준 키가 됩니다.

키를 단어 목록에 연결하는 해시 맵을 사용하면 한 번의 순회로 모든 단어를 그룹화할 수 있습니다. 각 단어마다 최대 8개 글자를 한 번 정렬하고 맵을 한 번 조회하면 되며, 다른 그룹과 비교할 필요는 없습니다.

순서를 유지하려면 첫 번째 접근 방식처럼 그룹화하기 전에 입력을 정렬하세요. 단어가 알파벳순으로 들어오므로 각 목록은 순서대로 채워지고, 그룹의 첫 단어가 들어올 때 키가 맵에 추가됩니다. 삽입 순서를 유지하는 맵(Python dict, JavaScript Map, Java LinkedHashMap, Dart map, Ruby 해시, PHP 배열)은 그룹을 그 순서대로 반환합니다. 맵에 순서가 없으면 각 그룹의 인덱스를 맵에 저장하고 그룹 자체는 목록에 저장하세요.

입력을 정렬하면 최대 k개의 글자를 비교하며 약 n log n번 비교합니다. 4000개 단어라면 약 5 × 10^4회의 단어 비교로, 8 × 10^6회 대신 훨씬 적습니다. 키를 만드는 데 O(n · k log k)가 추가되지만, k ≤ 8이므로 이에 비하면 작은 비용입니다.

알고리즘

단어를 알파벳순으로 정렬합니다.
각 단어의 글자를 정렬하여 키를 만듭니다.
해시 맵에서 키를 찾습니다. 새 키라면 해당 키의 빈 그룹을 만들고, 그룹은 생성한 순서대로 유지합니다.
단어를 해당 키의 그룹에 추가합니다.
각 그룹의 단어를 공백 하나로 연결하고, 그룹은 생성 순서대로 반환합니다.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

함정과 경계 사례

그룹화는 사람들이 연습하는 부분입니다. 이 버전에서 대부분의 오답은 출력 순서와 중복되지 않는 키에서 비롯됩니다.

그룹의 첫 단어가 아니라 키를 기준으로 그룹을 정렬합니다. 키는 단어들 중 하나가 아니라, 단어들을 재배열해 만든 가장 작은 값입니다. ["cab", "bad"]의 경우 키는 abc와 abd이므로 cab가 먼저 오지만, 첫 단어를 기준으로 하면 bad가 먼저 옵니다.
단어를 집합에 모읍니다. ["b", "a", "b"]는 b b를 반환해야 하지만, 집합은 하나만 남깁니다.
고유한 문자만으로 키를 만듭니다. ab와 aabb는 같은 두 문자를 사용하지만, aabb에는 각 문자가 두 개씩 있으므로 애너그램이 아닙니다.
문자 코드 값을 더해 키를 만듭니다. ad와 bc의 합은 같으므로, 합을 사용하면 문자가 하나도 겹치지 않는 단어들이 하나로 합쳐집니다.
각 그룹은 정렬하지만 입력은 정렬하지 않고, 그룹 정렬을 잊습니다. 그러면 삽입 순서는 첫 단어가 아니라 입력 순서가 됩니다.
직접 이어 붙이고 그룹 문자열의 시작이나 끝에 공백을 남깁니다.

자주 묻는 질문4

애너그램 그룹화의 시간 복잡도는 얼마인가요?

정렬된 문자를 키로 사용하는 해시 맵에서는 최대 k개의 문자를 가진 n개의 단어에 대해 키를 만드는 데 O(n · k log k)가 걸리고, 맵 작업에는 O(n · k)가 걸립니다. 이 버전은 출력 순서를 정하기 위해 단어도 정렬하므로 O(n · k · log n)가 추가됩니다. 키와 그룹에 필요한 공간은 O(n · k)입니다.

각 단어를 정렬하는 것보다 문자 개수 키를 사용하는 것이 더 빠를까요?

카운트 키는 26개의 문자 개수를 1#0#2#…와 같은 텍스트로 나열한 것으로, O(k log k) 대신 O(k)의 시간이 걸리므로 긴 단어에서 더 유리합니다. 길이가 최대 8자인 단어에서는 정렬도 그만큼 빠르며, 출력의 알파벳순 정렬에는 어느 키보다도 더 많은 비용이 듭니다. 두 단어의 문자 개수가 같을 때, 그리고 그때에만 정렬된 문자가 같으므로 두 키 모두 올바릅니다.

문자 코드의 합을 키로 사용하지 않는 이유는 무엇인가요?

서로 다른 글자들이 같은 합계를 만들 수 있습니다. a + d는 b + c와 같으므로 ad와 bc는 같은 그룹에 속하게 됩니다. 애너그램끼리는 같은 키를 갖고 그 외의 모든 경우에는 달라야 하며, 글자를 정렬하거나 각 글자의 개수를 모두 세면 이를 보장할 수 있습니다. 글자마다 소수 하나씩 곱하는 방법도 정확하지만, z에 101을 사용하면 z가 열 개 있는 단어는 이미 64비트 정수의 범위를 넘습니다.

그룹화하기 전에 입력을 정렬하는 이유는 무엇인가요?

정답은 각 그룹의 첫 번째 단어를 기준으로 정렬된 그룹을 요구합니다. 모든 단어를 한 번 정렬하면 두 가지를 모두 얻을 수 있습니다. 각 그룹에는 알파벳순으로 단어가 들어가고, 첫 번째 단어가 도착할 때 그룹이 만들어집니다. 그다음 각 그룹을 정렬하고 첫 번째 단어를 기준으로 그룹들을 정렬해도 같은 결과를 얻지만 코드가 더 많아집니다.

Python

def groupAnagrams(strs):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

기대값

["apple", "enlist listen silent", "notes onset stone tones"]