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은 아무것과도 일치하지 않으며, 첫 단어 기준으로는 선두입니다.

입력: 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는 짝이 없으며 맨 앞에 옵니다.

후속 질문

단어에 어떤 유니코드 문자든 들어갈 수 있다면, 정렬된 글자 또는 글자 수 중 어떤 키가 여전히 작동할까요? 그리고 그 키에서 무엇을 바꾸면 될까요?

힌트

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

3개 중 0개 열림

풀이

각 단어에서만 키를 계산하되, 그 단어의 모든 애너그램에 대해서는 같고 다른 모든 단어에 대해서는 다르게 만드세요. 단어의 문자를 정렬한 순서가 이러한 키가 되며, 키에서 그룹으로 매핑하는 해시 맵을 사용하면 한 번의 순회로 그룹을 모을 수 있습니다. 단어를 먼저 정렬하면 필요한 순서를 추가 작업 없이 얻을 수 있습니다.

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

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

핵심 아이디어

그룹 목록을 유지하고 각 단어를 모든 그룹의 첫 번째 단어와 비교합니다. 애너그램 관계는 추이적이므로 그룹마다 한 번만 비교하면 소속 여부를 결정할 수 있습니다. 두 단어는 길이가 같고 26개 문자 각각의 개수가 같을 때 애너그램입니다. 먼저 입력을 정렬하세요. 그러면 각 그룹의 단어가 알파벳순으로 추가되고, 그룹은 첫 번째 단어의 순서대로 만들어집니다.

두 단어도 애너그램이 아닌 경우, 각 단어는 자신보다 앞선 모든 그룹을 확인합니다. 단어 4000개라면 최대 8개 문자와 26개 카운터를 각각 확인하는 비교가 약 8 × 10^6회 발생합니다.

알고리즘

단어를 알파벳순으로 정렬합니다.
각 단어에 대해 첫 번째 단어의 글자 수가 같은 그룹을 찾아 해당 단어를 추가합니다. 일치하는 그룹이 없으면 새 그룹을 시작합니다.
각 그룹의 단어를 하나의 공백으로 연결하여 그룹이 만들어진 순서대로 반환합니다.

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가 됩니다. 두 단어의 글자 정렬 결과가 같은 경우는 두 단어가 같은 글자를 같은 횟수만큼 포함할 때이며, 이것이 애너그램의 정의입니다. 그러면 키에서 단어 목록으로 연결되는 해시 맵이 한 번의 순회로 모든 단어를 그룹화하고, 어떤 단어도 다른 그룹과 비교되지 않습니다.

순서는 이전과 마찬가지로 입력을 먼저 정렬해서 얻습니다. 각 목록은 알파벳순으로 채워지고, 그룹의 첫 단어가 도착할 때 키가 맵에 들어갑니다. 삽입 순서를 유지하는 맵은 그룹을 그 순서대로 반환합니다. 그렇지 않다면 그룹을 목록에 저장하고 각 키를 해당 인덱스에 매핑합니다.

입력을 정렬하는 데 드는 비용은 단어 4000개에 대해 약 5 × 10^4회의 단어 비교로, 8 × 10^6회보다 적습니다.

알고리즘

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

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는 같은 두 글자를 사용하지만 애너그램이 아닙니다.
각 그룹은 정렬하지만 입력은 정렬하지 않고, 그룹도 정렬하지 않는 것. 그러면 삽입 순서는 첫 번째 단어가 아니라 입력을 따릅니다.

자주 묻는 질문3

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

정렬된 문자 키를 만드는 데는 최대 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비트 정수의 범위를 넘습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

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

예상 출력

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