코딩 테스트 대비! 파이썬으로 "그룹 애너그램" 문제 풀이

파이썬으로 "그룹 애너그램" 문제 풀이


문제 설명

문자열 배열 strs가 주어졌을 때, 애너그램 단위로 그룹화하여 리스트를 반환하는 프로그램을 작성하세요. 애너그램이란 문자를 재배열하여 다른 뜻을 가진 단어로 바꿀 수 있는 것을 말합니다.


제약 조건

- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
- strs[i]는 소문자로만 이루어져 있습니다.


예시 입출력

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


솔루션 코드

from collections import defaultdict

def group_anagrams(strs):
    anagrams = defaultdict(list)
    
    for word in strs:
        # 정렬하여 애너그램 여부 판별
        sorted_word = ''.join(sorted(word))
        anagrams[sorted_word].append(word)
        
    return list(anagrams.values())

# 테스트
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
print(group_anagrams([""]))  # [['']]
print(group_anagrams(["a"]))  # [['a']]

코드 설명

1. 그룹화된 애너그램을 저장할 defaultdict를 생성합니다.
2. strs를 순회하며 각 문자열을 정렬합니다.
3. 정렬된 문자열을 키로 하여 해당 문자열을 애너그램 그룹에 추가합니다.
4. defaultdict의 값들을 리스트로 반환합니다.

이 풀이의 시간 복잡도는 O(n * k log k)이며, 공간 복잡도는 O(n * k)입니다. 여기서 n은 strs의 길이, k는 문자열의 최대 길이입니다.

이 문제에서는 문자열 정렬을 통해 애너그램 여부를 판별하는 방법을 사용합니다. 문자열을 정렬하면 애너그램은 동일한 문자열이 되므로, 이를 키로 하여 그룹화할 수 있습니다. defaultdict를 활용하여 코드를 간결하게 구현했습니다.

이런 유형의 문자열 처리 문제는 코딩 인터뷰에서 자주 출제되므로 숙지할 필요가 있습니다. 또한 애너그램 판별 방법 외에도 문자 카운팅, 정렬 등 다양한 기법을 익혀둘 필요가 있습니다.