이 글에서는 Python 3.x의 counter() 함수를 사용하여 두 문자열을 아나그램(anagram) 관계로 만드는 방법을 알아봅니다. 입력 문자열에서 임의의 문자를 자유롭게 제거할 수 있으며, 아나그램 관계를 성립시키기 위해 제거해야 하는 문자의 최소 개수까지 함께 구해보겠습니다.
먼저 아나그램의 정의부터 살펴보겠습니다. 두 문자열이 같은 종류의 알파벳을 순서와 무관하게 동일하게 포함하고 있을 때, 이 둘을 서로 아나그램이라고 부릅니다. 예를 들어 'listen'과 'silent'는 같은 문자들로 이루어져 있으므로 아나그램입니다.
counter() 메서드는 Python의 collections 모듈에 포함되어 있습니다. 따라서 counter() 함수를 사용하려면 먼저 collections 모듈을 import해야 한다는 점이 전제 조건입니다.
알고리즘
1. collections 모듈의 Counter(inp_str)를 사용해 입력 문자열을 딕셔너리 형태로 변환합니다. 이때 각 문자가 키(key), 해당 문자의 빈도수가 값(value)이 됩니다. 2. 전체 키의 개수를 세고, 두 입력 문자열에서 변환된 딕셔너리 사이에 공통으로 존재하는 키의 개수를 셉니다. 3. 공통 키가 하나도 없다면, 두 문자열 모두에서 (두 딕셔너리 길이의 합)만큼 문자를 제거해야 합니다. 4. 공통 키가 존재한다면, (max(두 딕셔너리의 길이) - 공통 키 개수) 가 제거해야 할 문자 수가 됩니다.
collections.Counter는 딕셔너리의 하위 클래스(subclass)로, 인터프리터가 문자의 개수를 자동으로 계산해 줍니다. 덕분에 우리는 부분 문자열을 일일이 생성하거나 아나그램 여부를 직접 검사할 필요 없이, 간결한 코드로 문제를 해결할 수 있습니다.
예제 코드
# 두 문자열을 아나그램으로 만들기
from collections import Counter
def convertAnagram(str_1, str_2):
# 문자열을 딕셔너리 형태로 변환
dict_1 = Counter(str_1)
dict_2 = Counter(str_2)
keys_1 = dict_1.keys()
keys_2 = dict_2.keys()
# 두 키 목록의 키 개수를 각각 카운트
count_1 = len(keys_1)
count_2 = len(keys_2)
# 공통 키를 찾기 위해 키 집합(set)으로 변환 후 교집합 계산
set_1 = set(keys_1)
commonKeys = len(set_1.intersection(keys_2))
if (commonKeys == 0): # 공통 요소가 없음, 즉 모든 문자가 서로 다름
return (count_1 + count_2)
else: # 이미 일치하는 요소가 일부 존재함
return (max(count_1, count_2)-commonKeys)
str_1 ='Tutorials'
str_2 ='sTutalori'
str_3='Point'
print (convertAnagram(str_1, str_2))
print (convertAnagram(str_3, str_2))실행 결과
0 6
첫 번째 결과가 0인 이유는 'Tutorials'와 'sTutalori'가 이미 같은 문자들을 포함하고 있어 아나그램 관계이기 때문입니다. 반면 'Point'와 'sTutalori'는 공통 문자가 거의 없어 6개의 문자를 제거해야만 아나그램이 됩니다.
결론
이 글에서는 Python의 collections.Counter를 활용해 두 문자열의 문자 빈도를 비교함으로써, 아나그램 관계를 유지하기 위해 제거해야 하는 문자의 최소 개수를 구하는 방법을 배웠습니다. Counter를 사용하면 복잡한 문자열 처리 로직 없이도 효율적이고 가독성 높은 코드를 작성할 수 있으며, 이 기법은 문자열 빈도 분석이 필요한 다양한 알고리즘 문제에 널리 응용될 수 있습니다.