리트코드 49. 그룹 애너그램 (파이썬)

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

 

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

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

 

cf) An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

---

[접근 고민] 15분 하자. 10분 추가. 10분 추가

 

* 문제이해 

-_-;;; 

- 애너그램 단위???? 

-> 보인다. 

 

1)

그룹핑을 어떻게 해서 넣어준담? 

문자열 배열이 100개일 수도 있잖아. 미리 리스트를 만들어주는 짓(?)은 할 수 없어. 

-> list[0] 이런식으로 넣어줄 수 있을 것 같음

그럼 가장 작은 단위부터 차례대로 넣어주는거로 하고

이제 딕셔너리를 활용한다는 아이디어도 익숙해져보자.

 

2)

애너그램인지 어떻게 파악해줄까

우선 for i in strs 로 하나씩은 다 읽을건데

- 힌트는 다 3글자라는데 있을듯

eat

eta

aet

ate

tea

tae 

-> 순열이네. permutation 써서 같으면 애너그램으로 판정해주면 될 듯

정렬로 하는게 정석같은데... 순열로도 해도 될 것 같은데? 따로 해보자. 

 

3)'비교'라고 하면 나는 왜 2개씩 직접 비교해주는 것밖에 생각이 안드는지... ㅠ

-> 뭘 비교해야 같은 애너그램으로 볼텐데???

4) 가장 작은 단위대로 list에 넣어줘야 하는데, 가장 작은 단위는 또 어떻게 앎? 

    len() 으로 세어줘야 할 것 같은데, 그럼 새로운 리스트나 튜플이나 집합 만들어줘야 하는거 아님? 

 

// 

 

힌트 : 정렬하여 '딕셔너리'에 추가

---

[코드 짜기]

---

[올바른 코드를 확인해보자]

 

가장 간단한 방법은 '정렬(데이터의 집합을 어떠한 기준(핵심항목, key)의 대소관계를 따져 일정한 순서로 줄지어 세우는 것)하여 비교하는 것' 

-> 애너그램 관계인 단어들을 정렬하면 서로 같은 값을 갖게 될 것

 

(1) sorted()는 숫자뿐만 아니라 문자열도 잘 정렬해서, '리스트'로 반환 ex) ['a', 'b' ...]

-> 딕셔너리 내 key값으로 활용하기 위해서, join() 사용해서 문자열로 결합

 

(2) 애너그램끼리는 같은 key를 같게 되고, 여기에 append() 하는 형태

 

cf) sort() 

- 리스트 '자체'를 정렬해서 별도 추가 공간을 필요로 하지 않음

- 제자리 정렬(in-place-sort)라고도 부름

- 리턴값이 없음. 정렬 결과를 별도로 리턴하는 sorted()와는 다름! 

 

cf) sorted()  

- key = 옵션을 지정해 정렬을 위한 키, 함수를 별도로 지정 가능 (함수는 함수 정의 해주고, key=함수명 해주면 됨)

c = ['ccc', 'aaaa', 'd', 'bb']
result = sorted (c, key=len)

print(result) 
#  ['d', 'bb', 'ccc', 'aaaa']

 

구글링해서 찾은 더 자세한 설명

같은 애너그램 단위로 묶으라는 것은 결국 단어 안의 알파벳 종류와 갯수가 같은 단어끼리 묶어서 출력하라는 뜻 같다.
즉, 예시처럼 'eat', 'tea', 'ate' 세 단어는 모두 'a' 1개, 'e' 1개, 't' 1개로 구성되어 있어서 같은 그룹으로 묶을 수 있다.
 
1. 입력된 strs의 원소인 단어들을 알파벳 별로 쪼개고, 정렬시키면, 같은 알파벳으로 구성된 애너그램들은 똑같은 결과물이 나온다.
2. 같은 애너그램을 가진 원소들끼리 묶어야 하므로, 애너그램을 key, 원래 단어를 value로 하는 딕셔너리를 만든다.
3. 출력이 count값이 아니라, 원래 단어들이 묶인 리스트이기 때문에, 같은 key인 단어가 나올 때마다 value 리스트에 원소를 추가하는 식으로 만든다.
 
참고: 1. 과정을 실행하면서 알게 된 사실인데, attriute 인 .sort()의 경우 문자열에 적용할 수 없는 반면, 내장함수인 sorted()의 경우 문자열에도 잘 적용이 되었다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = {}
        for str in strs:
            s = ''.join(sorted(str))
            result[s] = result.get(s,[]) + [str]
        return result.values()

이분의 설명으로 더욱 이해를 할 수 있게 됨. 코드도 이분 거
https://rollingsnowball.tistory.com/117

 

//

 

s = ''.join(sorted(str))

result[s] = result.get(s,[]) + [str]

- key가 s일때마다 (정렬한 key값이 같을 때마다), [str]을 넣어준다...까지는 이해가 되는데 앞에는 뭐지?

->  key값이 s일 때의 value값... 

 

쥬피터로 출력해본거

cf) 반면에 result[s] = [str]로만 하면 다음과 같이 나옴 

->

result[s] = [str]

print(result)

 

{'aet': ['eat']}

{'aet': ['tea']}

{'aet': ['tea'], 'ant': ['tan']}

{'aet': ['ate'], 'ant': ['tan']}

{'aet': ['ate'], 'ant': ['nat']}

{'aet': ['ate'], 'ant': ['nat'], 'abt': ['bat']}

"""

 

// 

 

오케이.

이전에 애너그램 같았던 것도 넣어줘야 함을 인지.

근데 get(s, []) 이렇게하면 리스트 형식으로 넣어주고, 또 리스트끼리 더하기 가능?

-> 리스트끼리 더하기는 너무나 가능!

-> 딕셔너리에서 없는 key값을 가지고 오면 오류가 나기때문에 defaultdic() 기능겸 넣어준 것

 

return result.values()

---

import collections

def groupAnagrams(self, strs):
    anagrams = collections.defaultdict(list) # 디폴트값을 list로 줌

    for word in strs:
        # 정렬하여 딕셔너리에 추가
        anagrams[''.join(sorted(word))].append(word)

    return list(anagrams.values())

내 사고 흐름으로는 이 코드가 더 잘맞긴 하다.

위에 코드는 직접 더해주는 느낌이라서 끌어왔다면, 이 코드는 직관적으로 바로 넣어주는! 느낌