ch6-5(leetcode 49). 그룹 애너그램

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 49번 ( https://leetcode.com/problems/group-anagrams/ )

 

풀이방법 1. 

주어진 입력을 그대로 사용하지 않고 변형한 뒤 사용하면 쉽게 풀 수 있는 문제였다. 

특히 리스트가 주어졌지만 리스트의 인덱스를 리턴하는 문제가 아니라면 입력으로 주어진 리스트의 순서를 바꿔도 된다는 생각을 해 보면 좋겠다. 

 

문자열 A와 B가 서로 애너그램일 경우, 문자열 A의 모든 문자를 단 한 번씩 사용해서 문자열 B를 나타낼 수 있으며, 그 반대도 성립한다. 

서로 애너그램인 문자열들은 여러 개가 있을 수 있으며, 그 문자열들을 하나의 리스트로 묶기 위해서는 그 문자열들을 다른 문자열들과 구분할 수 있어야 한다. 

 

특정 애너그램을 구성하는 문자열들은 모두 같은 문자열로 구성되어 있다. 해당 문자열을 알파벳 순서로 정렬하면, 각 애너그램에 따른 unique한 값을 얻을 수 있다. 

즉 속한 애너그램이 다르면 문자열의 값이 다르게 나오기 때문에 서로 애너그램인지 아닌지를 구분할 수 있는 것이다. 

 

이 원리를 이용하고, dictionary 자료형을 사용하면 각 애너그램들을 묶어서 저장할 수 있다. 

key 값으로는 문자열을 정렬한 값이 할당되고, value 값으로는 해당 key 값으로 나타낼 수 있는 문자열 리스트가 할당된다. 

 

 

다만 문자열을 정렬하기 위해서 필요한 sort()와 sorted() 중, sorted()는 iterable 자료형은 모두 매개변수로 받을 수 있기 때문에 문자열도 매개변수로 받을 수 있다.

(각 인덱스 값을 돌아가면서 리턴하는 것이 가능하므로, 문자열도 iterable이다)

그러므로 sorted()를 사용해서 문자열을 리스트로 변환한 뒤, 다시 join을 사용해서 리스트를 문자열로 변환한다. 

 

다만 join은 A와 B를 합치는 함수이므로, 대상이 될 A 문자열이 필요하다. 

공백 문자열에다가 join을 사용하면 해당 리스트만 문자열로 반환할 수 있다. 

key = "".join(sorted(string))
dicts[key].append(string)

 

이후 values() 메소드를 사용해서 dictionary 안에 속한 모든 값 리스트를 리턴하면 된다.