문자열로 이루어진 리스트 words가 주어졌을 때, 서로 애너그램(Anagram) 관계에 있는 단어들을 하나의 그룹으로 묶고, 그중 가장 큰 그룹의 크기를 반환하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 다음과 같다고 가정해 봅시다.
words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
여기서 "xyz", "zyx", "yzx"는 모두 같은 문자들로 이루어진 애너그램이므로 하나의 그룹이 되고, 이 그룹의 크기는 3입니다. 따라서 출력 결과는 3이 됩니다.
문제 해결 접근 방법
애너그램의 핵심 특징은 문자를 사전순(lexicographical order)으로 정렬하면 모두 동일한 문자열이 된다는 점입니다. 예를 들어 "xyz", "zyx", "yzx"를 각각 정렬하면 모두 "xyz"가 됩니다.
이 특성을 활용하면 다음과 같은 순서로 문제를 해결할 수 있습니다.
- 빈 딕셔너리(맵) lookup을 생성합니다. 여기에는 정렬된 문자열을 키로 하고, 해당 애너그램 그룹의 개수를 값으로 저장합니다.
- 결과값 res를 0으로 초기화합니다.
- words 리스트의 각 단어 i에 대해 반복합니다.
- 단어 i를 사전순으로 정렬하여 문자열 p를 만듭니다.
- p가 lookup에 이미 존재하면 개수를 1 증가시키고, 없으면 1로 설정합니다.
- res와 lookup[p] 중 더 큰 값을 res에 저장합니다.
- 반복이 끝나면 res를 반환합니다. 이것이 곧 가장 큰 애너그램 그룹의 크기입니다.
아래 예제 코드를 통해 더 자세히 살펴보겠습니다.
구현 예제 코드
class Solution:
def solve(self, words):
lookup = {}
res = 0
for i in words:
p = "".join(sorted(i))
lookup[p] = lookup.get(p, 0) + 1
res = max(res, lookup[p])
return res
ob = Solution()
words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
print(ob.solve(words))입력
["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
출력
3
코드 설명
sorted(i)는 문자열을 문자 단위로 정렬한 리스트를 반환하고, "".join()을 통해 다시 하나의 문자열로 합칩니다. 이렇게 만든 정렬된 문자열이 애너그램 그룹을 구분하는 키 역할을 합니다.
lookup.get(p, 0)은 딕셔너리에 키 p가 없으면 기본값 0을 반환하므로, 키 존재 여부를 별도로 검사하지 않고도 개수를 손쉽게 증가시킬 수 있습니다. 매 반복마다 max(res, lookup[p])로 최대 그룹 크기를 갱신하기 때문에, 마지막에 res에는 가장 큰 애너그램 그룹의 크기가 저장됩니다.
시간 복잡도
각 단어의 길이를 k, 단어의 개수를 n이라 할 때, 각 단어를 정렬하는 데 O(k log k)가 소요되므로 전체 시간 복잡도는 O(n · k log k)입니다. 공간 복잡도는 딕셔너리에 저장되는 키의 수에 비례하여 O(n · k)입니다.