리트코드(LeetCode) 49번 그룹 애너그램(Group Anagrams)

---

 

문제를 풀기 전에 파이썬에서의 정렬, 그리고 defaultdict에 대한 간단한 정리를 하고 풀어보도록 하자

 

 

---

파이썬에서의 정렬

파이썬에서의 정렬은 기본적으로 팀 소트(TimSort)를 이용한다.

팀 소트는 사실상 병합 정렬과 퀵 정렬을 제치고 현업에서 가장 널리 쓰이는 정렬 알고리즘이다.

 

 

파이썬에서 쓰는 기본적인 정렬은 다음과 같이 사용한다.

a = [2, 5, 1, 9, 7]
a_sort = sorted(a)
print(a)
print(a_sort)

#출력값
#[2, 5, 1, 9, 7]
#[1, 2, 5, 7, 9]

 

 여기서 주의해야 할 점은 제자리 정렬(In Place Sort)과 정렬 결과를 별도로 리턴하는 sorted( )는 다르다는 점이다.

 

#제자리 정렬(In place Sort)
#정렬 결과를 별도로 리턴하는 sorted()와 다르므로 주의
a.sort()
print(a)

#출력값
#[1, 2, 5, 7, 9]

 

또한 sort함수는 숫자 뿐 아니라 문자도 정렬 가능하다.

#숫자 뿐 아니라 문자도 정렬가능
b = "zbdaf"
b_sort = sorted(b)
print(b_sort)

#출력값
#['a', 'b', 'd', 'f', 'z']

 

 

다시 문자열로 결합하려면 join() 함수를 사용하면 된다.

b_sort = "".join(b_sort)
print(b_sort)

#출력값
#abdfz

 

sorted()는 key = 옵션을 지정해 정렬을 위한 키 또는 함수를 별도로 지정할 수 있다.

다음은 옵션을 지정하는 정렬에서 옵션을 함수의  길이를 구하는 len으로 지정한 경우이다.

 

#sorted()는 key = 옵션을 지정해 정렬을 위한 키 또는 함수를 별도로 지정할 수 있음
#다음 코드는 정렬을 위한 함수로 길이를 구하는 len을 지정한 경우이다.
c = ['ccc', 'aaaa', 'd', 'bb']
c_sort = sorted(c, key = len)
print(c_sort)

#출력값
#['d', 'bb', 'ccc', 'aaaa']

 

함수를 이용해 키를 정의하는 방법 중 우선순위로 첫 문자열(s [0])과 그다음 우선순위로 마지막 문자열(s [-1])을 이용해 정렬해보겠다.

 

d = ['cde', 'cfc', 'abc']
d_sort_A = sorted(d)
d_sort_B = sorted(d, key = lambda x : (x[0], x[-1])) #람다식을 이용

#그냥 sort를 사용했을 때는 abc가 먼저 나오고 c를 비교한다음 그 다음 두번째 문자열인 d와 f를 비교해 cde가 먼저 나오지만
#sort에 key를 넣어주면 먼저 첫번째 글자를 비교해주고 그 다음 마지막 문자열인 e와 c를 비교해 cfc가 먼저 나오게 된다.
print(d_sort_A)
print(d_sort_B)

#출력값
#['abc', 'cde', 'cfc']
#['abc', 'cfc', 'cde']

 

 

---

defaultdict

defaultdict이란 존재하지 않는 키를 삽입하려해도 error가 나지 않는 딕셔너리이다. (말 그대로 default값이 주어지기 때문)

 

 

다음은 default값이 int인 딕셔너리이다.

#defaultdict -> 존재하지 않는 키를 삽입하려해도 error가 나지 않는 딕셔너리
from collections import defaultdict

#default 값이 int 인 딕셔너리
#value를 지정하지 않으면 default값으로 0이 들어가게 된다.
int_dict = defaultdict(int)
int_dict['key1']
int_dict['key2'] = 5
print(int_dict)

#출력값
#defaultdict(<class 'int'>, {'key1': 0, 'key2': 5})

 

 

다음은 default값이 list인 딕셔너리이다.

 

 

#default값이 list 인 딕셔너리
#value를 지정하지 않으면 default 값으로 빈 리스트가 들어가게 된다.
list_dict = defaultdict(list)
list_dict['key1']
list_dict['key2'] = [1,2,3]
print(list_dict)

#출력값
#defaultdict(<class 'list'>, {'key1': [], 'key2': [1, 2, 3]})

 

 

---

문제

문제를 보면 애너그램끼리는 sort로 정렬하면 같은 단어를 key로 가질 수 있다는 사실을 파악해야 한다.

그렇게 같은 문자열을 key로 갖는 애너그램들을 value값들로 정리한 다음 그 value들을 return 하면 된다.

from collections import defaultdict

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

anagrams = defaultdict(list)
for word in strs:
    anagrams["".join(sorted(word))].append(word)
    
return list(anagrams.values())