49. Group Anagrams (Medium) [Python]

문제

 

와... 처음 풀어보는 Medium문제...

Hash Map을 사용하는 건 짐작을 하였지만, 도무지 풀 방법을 몰라서 30분 고민하고 풀이를 찾아보았다

풀이 출처: https://www.youtube.com/watch?v=vzdNOK2oB2E&ab_channel=NeetCode

혹시 이해한게 틀린 수 있으니 지적해주시면 감사하겠습니다.

 

생각 방식

a부터 z는 26개의 character이고, 한 단어에 이 character들이 얼마나 나오는지 체크를 한다

그리고 같은 anagram끼리 묶어서 출력을 해주면 된다.

 

이해하기 어려웠던 점들

일단 Hash Map의 구성부터 애를 많이 먹었다

 

풀이를 보면서 아이패드로 노트를 남겼는데 도무지 저 key에 뭐가 들어가는지 이해가 안 됐다...

그래서 GPT를 돌려서 어떻게 구성된건지 찾아봤다

{(1, 0, 0, ..., 0): ['bat'], (1, 1, 1, ..., 0): ['eat', 'tea', 'ate'], (1, 0, 1, ..., 1): ['tan', 'nat']}

 

이런 식으로 이 string에 각 character가 몇 번이 들어가는지를 나타낸 tuple이 key가 되는 거였다...

 

defaultdict(list)는 우리의 딕셔너리에 값을 리스트로 지정해준다는 것으로 이해했다

참고: 위에 참고한 유튜브 밑에 댓글과 https://www.geeksforgeeks.org/defaultdict-in-python/

 

그리고 ord()는 분명히 학교에서 배운 내용인데 기억이 가물가물했다

그래서 찾아보니 ord()는 number representing the unicode code of a specified character 였다

예) ord("a")는 97  ord("z")는 122이다

 

그래서 count[ord(c) - ord("a")] += 1 는 a부터 z가 나오는 횟수를 지정해준다고 이해했다

 

그리고 res[tuple(count)].append(s)

⭐️ 기억하자: list는 key가 될 수 없다 

위에 설명했던 것처럼, 우리의 key는 튜플이다. 그래서 count를 튜플로 변환해 주고 거기에 우리의 값인 s를 넣는 방식이다

 

마지막으로 value만 리턴하면 되니까, values()로 리턴을 받으면 된다

 

💻 코드

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list) # define a dictionary with values as a list

        for s in strs:
            count = [0] * 26 # a-z 26개의 character로 되어있으니까
            for c in s:
                count[ord(c) - ord("a")] += 1 #increment the count of frequency of each character in the string.
            
            res[tuple(count)].append(s) # in Python, list cannot be keys, tuples are non mutable

        return res.values()

 

 

내 것으로 만드는 데에 필요한 시간이 정말 많이 소요됐다 (아마 1시간 30분은 걸린듯...)

며칠 뒤에 또 다시 풀어봐야겠다...