[Python] 문자열 애너그램(Anagrams) | Counter(), DefaultDict()

이 문제를 풀다가 애너그램을 찾는 방법에 대해서 정리해본다.

풀이를 하며 Counter를 이용한 방법과 DefaultDict를 이용한 방법 2가지를 배웠다.

요구사항

우선 문제의 요구사항을 정리해보면 이렇다.

 

애나그램 : 첫번째 문자열을 재배열했을때 두번째문자열이 되면, 두개의 문자열들은 애나그램 쌍이라고 칭한다.
두 문자열을 구성한 알파벳이 같아야하고, 그 알파벳들의 frequency도 같아야함
ex: bacdc와 dcbac는 애나그램
ex: bacdc와 dcbad는 애나그램이 아니다.(문자열길이는 다를수도 있음)

두개의 문자열을 애나그램으로 만들기 위해 필요한 최소문자 삭제수는?
ex : a=cde, b=dcf
1.a에서 e삭제
2.b에서 f삭제
a=cd, b=dc -> 애나그램
리턴값 : 2

 

즉, 문자열1을 구성한 알파벳이 문자열2에 모두 있어야하고 반대로 문자열2의 알파벳이 모두 문자열1에 있어야한다.

그리고 그 알파벳들의 빈도수까지 같아야 한다는 것이 핵심이다.

서로 문자열이 포함되어 있는지는 단순하게 IN 으로 확인할 수 있다.

 

나의 접근방법

문자열끼리 서로 알파벳의 구성을 확인하고, 또 추가적으로 빈도수를 세는 방식을 처음에 생각했다.

하지만 두번의 작업으로 구분하기엔 너무 비효율적이다. 

그냥 문자열끼리 빈도수의 그 차이를 알면

차이가 0일경우 같다는 의미가 되기 때문에

굳이 문자열의 구성이 같은지를 확인할 필요가 없다는 것을 알게 되었다.

 

Counter() 사용방법 

그래서 counter()함수를 사용해 각 문자열의 알파벳 빈도수들을 계산했다.

 

collections 모듈의 Counter 클래스는

별도 패키지 설치 없이 파이썬만 설치되어 있다면 다음과 같이 임포트해서 바로 사용가능하다.

from collections import Counter

 

아, counter()값들끼리 연산도 가능했다.

그래서 a의 알파벳 빈도수 - b의 알파벳 빈도수는 = a의 알파벳에서 중복된 알파벳을 지우고 남은 a의 알파벳들이다.

반대로 b의 알파벳 빈도수 - a의 알파벳 빈도수는 = b의 알파벳에서 중복된 알파벳을 지우고 남은 b의 알파벳들이다.

결국 이제 이 둘을 합치면 서로의 문자열에서 나타나지 않은 문자열들만 모을 수 있게 된다.(리스트)

그래서 그 문자열들의 개수(리스트 크기)를 리턴하면 된다. 

from collections import Counter
def makeAnagram(a,b):
    a = Counter(a) #Counter({'o': 2, 's': 1, 'h': 1, 'w': 1, 'm': 1, 'a': 1, 'n': 1})
    b = Counter(b) #Counter({'w': 1, 'o': 1, 'm': 1, 'a': 1, 'n': 1})
    c = a - b #Counter({'s': 1, 'h': 1, 'o': 1})
    d = b - a #Counter()
    e = c + d #Counter({'s': 1, 'h': 1, 'o': 1})
    
    return len(list(e.keys()))

a=input() #shoowman
b=input() #woman
res=makeAnagram(a,b)
print(res) #3

 

추가적으로 counter()를 통해 다음과 같은 추가적인 메소드를 제공한다. 

counter.most_common() : 빈도수가 가장 많이 나타난 순서대로 배열을 리턴한다. 

counter.most_common(n=2) : 빈도수가 가장 많이 나타난 key와 value(빈도수)를 사이즈(n)의 배열로 리턴한다. 

from collections import Counter

a="shoooowwman"
a=Counter(a)

print(a.most_common()) 	  # [('o', 3), ('w', 2), ('s', 1), ('h', 1), ('m', 1), ('a', 1), ('n', 1)]
print(a.most_common(n=2)) #[('o', 3), ('w', 2)]

 

또는 아래와 같은 방법으로도 counter()대신 사용이 가능하다. 

DefaultDict() 사용방법

기존 dict={} 로 선언하는 방식과 다르게 

어떤 키(key)에 대한 값(value)이 없는 경우에 대한 처리를 해줄 수 있다.

 

예를 들어, 주어진 단어에 들어있는 알파벳의 글자수를 세서 counter라는 dict에 아래와같이 저장할 수 있다.  

for 루프안에서 if조건을 통해 counter사전에 어떤 글자 key가 존재하지 않는 경우 기본값을 0으로 세팅해주었다. 

def countLetters(word):
    counter = {}
    for letter in word:
        if letter not in counter:
            counter[letter] = 0
        counter[letter] += 1
    return counter

 

하지만 default() 사용하면

이렇게 key가 없는 경우 별도로 if문으로 처리하지 않아도된다. 

 

collections 모듈의 defaultdict 클래스는

별도 패키지 설치 없이 파이썬만 설치되어 있다면 다음과 같이 임포트해서 바로 사용가능하다.

from collections import defaultdict

 

생성자로 기본값을 생성해주는 함수(ex : int) 를 넘기면,

모든키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다. 

from collections import defaultdict

def countLetters(word):
    counter = defaultdict(int)
    for letter in word:
        counter[letter] += 1
    return counter

default()의 생성자로 int로 넘겨 key가 없는 경우 0 으로 리턴하도록 했다. 

 

 

출처 

Counter 사용법

https://www.daleseo.com/python-collections-counter/

[파이썬] collections 모듈의 Counter 클래스 사용법

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=wideeyed&logNo=221540885097 

[Python] Collections.Counter 사용법

DefaultDict()사용법

https://www.daleseo.com/python-collections-defaultdict/

[파이썬] 사전의 기본값 처리 (dict.setdefault / collections.defaultdict)