[파이썬 알고리즘] 그룹 애너그램

그룹 애너그램

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

입력
["eat", "tea", "tan", "ate", "nat", "bat"]

출력
[
    ["ate", "eat", "tea"],
    ["nat", "tan"],
    ["bat"],
]

code: most_common.py

*애너그램이란?

문자를 재배열하여 다른 단어로 바꾸는 것.

위의 경우에는 문자 순서를 바꾸어 다른 문자로 바꿀 수 있는것끼리 묶는것을 말하는것이다.

---

같은 애너그램에 포함되는 단어의 공통점은 sort했을때 스펠링이 같다는 점이다.

따라서 애너그램의 집합인 dictionary를 선언한 뒤, 각 word를 sort 하였을때의 값을 key로 삼고 dictionary에 삽입한다.

각 애너그램에 처음 삽입했을 때 존재하지 않는 키에 값을 삽입하면 keyError가 발생할 수 있는데, 해결방법은 두가지가 있다.

먼저, dictionary.get, dictionary.in을 활용하여 키값이 존재하는지 확인할 수 있는데,

get은 존재할 경우 그 키에 저장된 값들을 return 하고

in은 true/false로 존재 여부만 return한다.

그다음 방법은 collections모듈의 defautdict를 활용하여 dictionary를 생성하는 방법인데, 이 방법을 이용하면 항상 기본값이 선언된 것처럼 비교구문을 생략할 수 있다.

코드는 다음과 같다.

def mostCommon(paragraph, banned):
    words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
             .lower().split()
             if word not in banned]

    counts = collections.Counter(words)
    print(counts)
    return counts.most_common(1)[0][0]