[ 6. 문자열 조작 ] - 그룹 애너그램(Group Anagrams)

📍 그룹 애나그램

애너그램 이란 일종의 말장난으로 어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다. 예를들면 listen의 알파벳을 다시 조합하면 silent가 되는것이 있다.

---

⚡️ 나의 풀이

어찌됐건 애나그램은 문자열 하나씩 분리해서 재 조합하는것이기 때문에 같은 알파벳이 쓰였는지 확인하려면 하나씩 분리해서 정렬하면 된다.

예를 들어, 문제 입력 strs = ["eat","tea","tan","ate","nat","bat"]을 기준으로 설명하면 strs를 반복문으로 하나씩 정렬하면 다음과 같은 결과가 나온다.

strs = ["eat","tea","tan","ate","nat","bat"]
for i in strs:
    print(sorted(list(i)), i)

'''
['a', 'e', 't'], eat 
['a', 'e', 't'], tea
['a', 'n', 't'], tan
['a', 'e', 't'], ate
['a', 'n', 't'], nat
['a', 'b', 't'], bat
'''

같은 알파벳이 쓰인 단어를 정렬하면 출력이 동일하다는 것을 알 수 있다. 문제에선 같은 출력끼리 리스트로 묶어줬는데, 이는 defaultdict(list)를 이용하면 쉽게 접근 할 수 있다.

728x90

딕셔너리에서 key는 중복이 될 수 없기때문에 key 한개에 여러개의 value값을 줄 수있고, value값만 더해준다면 문제에서 요구하는 바를 충족시킬 수 있다. 또한, key값을 ''.join()형태와 tuple형태로 줄 수 있는데 둘 중 편한것을 사용하자.

 

이 문제를 풀면서 파이썬 알고리즘 인터뷰를 풀기전에는 팰린드롬 애나그램과 같이 문자열 특징을 이용한 문제를 풀어보지 못했는데, 한 유형에서도 여러가지 문제를 접할 수 있어 좋다.

from collections import defaultdict
strs = ["eat","tea","tan","ate","nat","bat"]

# ''.join()
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = defaultdict(list)
        for i in strs:
            result[''.join((sorted(list(i))))].append(i)
        return result.values()

# tuple
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = defaultdict(list)
        for i in strs:
            result[tuple(sorted(list(i)))].append(i)
        return result.values()