[leetcode 49.python] 그룹 애너그램 (Group Anagrams) 풀이

https://leetcode.com/problems/group-anagrams/

 

문제를 풀기 앞서 필자는 파이썬문법을 모르는 사람임을 밝힌다. 

그래서 파이썬 문법,용어도 공부하면서 풀기에 글이 길어질 수 있으며,

필자와 같은 상황에 처해있는 개발자에게는 아주 도움이 되는 글이 되겠다. 후에는 글을 쓸수록 문제풀이만 깔끔하게 할 수 있을 정도가 되길 바란다.

 

=> 내용이 너무 길어져 글을 따로 분리하기로했다. 문제에 필요한 정보들을 링크로 남겨둘 것이다. (하단 필요한 개념 참고)

 

---

문제 

문자열 배열을 받아 애너그램 단위로 그룸핑하라 

 

Example : 
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

 

 

---

필요한 개념

https://algoroot.tistory.com/50

[python] 파이썬의 자료형 List, Dictionary 리스트,딕셔너리

https://algoroot.tistory.com/51

[python] 파이썬 정렬 함수 sorted()

---

 

문제설명

 

파이썬문법을 모르는 상태에서 시작한 나는 문제를 보고 어떻게 풀지 생각하는 시간을 오래가지지 않았다. 5분정도 생각은 해보고 안되면 바로 풀이를 보며 한 줄씩 이해하는 방식으로 이해했다. 

 

문제는 애너그램 단위로 그룹핑하라는 것이었다. 

'애너그램'은 한 문자를 재 배열하여 다른 뜻을 가진 단어로 'eat' 을 'ate', 'tea'로 새로운 단어를 만드는 것과 같다. 

 

 

---

문제풀이

 

이런 애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. 

애너그램 관계인 단어들을 다시 정렬하면 서로 같은 값을 갖게 되기 때문이다. 

 

	a = "eat"	b="ate"	c="tea"
sorted() 정렬	sorted(a) >>> ['a', 't', 'e']	sorted(b) >>> ['a', 't', 'e']	sorted(c) >>> ['a', 't', 'e']
''.join() 공백없이 합치기	''.join(sorted(word)) > 'aet'	''.join(sorted(word)) > 'aet'	''.join(sorted(word)) > 'aet'

 

위 알아야할 개념을 통해 딕셔너리 개념을 알았다면,  존재하지 않는 키를 삽입할 경우 error가 발생한다는 것을 알고,

이 경우 defaultdic을 통해 해결할 수 있음을 안다. 

 

딕셔너리 key값은 중복될 수 없다. 따라서 "ate"를 key값으로 설정하고 for문을 통해 value에 정렬이 "ate" 로 되는 모든 문자를

key 가 "ate"인 value로 append()를 통해 담으면 되는 방식이다. 

 

참고로 딕셔너리의 key, value 정의 방식은 a = { 'key1' : 'value1'} 나중에 별도로 선언하는 방식은 a['key3'] = 'value3' 이었다. 

defaultedic을 통해 초기 value를 List로 주었기 때문에 나중에 별도로 선언하는 방식이 사용가능해진다. 

 

anagrams = collections.defaultdict(list)

anagrams[''.join(sorted('eat'))].append('eat')
# anagrams[ate].append('ate')
# {'aet' : 'eat'}

anagrams[''.join(sorted('eat'))].append('tea')
# anagrams[ate].append('tea')
# {'aet' : 'eat', 'tea'}

anagrams[''.join(sorted('eat'))].append('ate')
# anagrams[ate].append('ate')
# {'aet' : 'eat', 'tea', 'ate'}

만약 정렬이 'ate'로 안되는 경우인 'tan', 'nat', 'bat' 은 'tan'이 key값이 되어 tan' 'nat' 가 value로, 'abt'가 key값이 되어 'bat'이 value로 들어가게 된다.

 

 

그렇게 for문을 돌리면 아래와 같은 출력값이 나온다

defaultdict(<class 'list'>, {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']})

 

 

여기서 단어들만 나와야하기 때문에 우리는 value값만 뽑아주는 value()를 써서 정리해주면된다.

return amagrams.values()
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

 

---

 

문제답안

 

import collections
from typing import List

# 같은 애너그램 단위로 묶는다 = 단어의 알파벳 종류와 갯수가 같은 단어끼리 묶는다.

# 1. 입력된 strs의 원소인 단어들을 알파벳별로 쪼갠다 > 그 알파벳들을 정렬시키면 애너그램들은 같은 결과물이 나오게된다:

# 2. 같은 애너그램을 가진 원소들끼리 묶어야한다. 애너그램을 key, 원래 단어를 value로 하는 딕셔너리를 만든다.


# collections ? 파이썬의 내장모듈로 이 모듈에서는 defaultdic을 지원해줍니다. 
# key의 개수를 세어야하는 상황이나, list나 set의 항목을 정리해야하는 상황에 적절합니다.

# list_dict = collections.defaultdict(list)
# list_dic['key1']
# list_dic['key2'] = 'test'
# defaultdict(<class 'list'>, {'key1':[], 'key2':'test'})


# 문제풀이 
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # defaultdict : 존재하지 않는 key 로 인한 에러를 방지하기 위해서 사용
        # 기본값 초기화 안해줘도 자동으로 초기화 해준다. 예외처리할 때 편하다.
        anagrams = collections.defaultdict(list)
        # {}
        print(anagrams)

        for word in strs:
            # 정렬하여 딕셔너리에 추가 / 주어진 문자를 알파벳순으로 정렬하여 같은 에너그램을 key로 dic에 저장한다.
            anagrams[''.join(sorted(word))].append(word)
            # sorted(eat) => ['a', 'e', 't']
            # ''.join(sorted(word)) => 'aet'
            # anagrams['aet'].append(eat) = {'aet' : 'eat'}
            print(anagrams)
        return list(anagrams.values())



if __name__ == '__main__':
    s = Solution()
    print(s.groupAnagrams(["eat","tea","tan","ate","nat","bat"]))

 

 

Refrence : [책만] 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview