파이썬으로 애너그램 단어의 최대 부분 집합 크기 구하기

개요

소문자로 이루어진 문자열 배열이 주어졌을 때, 서로 애너그램(anagram) 관계에 있는 단어들로 구성된 가장 큰 부분 집합(subset)의 크기를 찾는 것이 이번 글의 목표입니다.

애너그램이란 한 문자열의 글자들을 단순히 재배열하여 다른 문자열을 만들 수 있을 때, 두 문자열이 서로 애너그램 관계에 있다는 의미입니다. 예를 들어 'python'과 'typhon'은 같은 글자들로 이루어져 있으므로 서로 애너그램입니다.

이 문제는 파이썬의 Counter() 메서드를 활용하면 매우 간단하고 빠르게 해결할 수 있습니다.

알고리즘

전체 풀이 과정은 다음 네 단계로 정리할 수 있습니다.

1단계: 공백으로 구분된 입력 문자열을 단어별로 분리합니다.
2단계: 문자열 목록에 있는 각 단어를 글자순으로 정렬합니다.
3단계: Counter 메서드를 사용해 정렬된 문자열을 키(key)로, 등장 빈도를 값(value)으로 하는 딕셔너리를 생성합니다.
4단계: max() 함수로 빈도수의 최댓값을 구합니다. 이 값이 곧 가장 큰 애너그램 부분 집합의 크기입니다.

여기서 핵심 아이디어는 애너그램 관계인 단어들은 글자를 정렬하면 모두 동일한 문자열이 된다는 점입니다. 따라서 각 단어를 정렬한 뒤 같은 문자열이 몇 번 등장하는지 세면, 그중 가장 많이 등장하는 횟수가 바로 정답이 됩니다.

예제 코드

# 서로 애너그램인 단어들 중
# 가장 큰 부분 집합의 크기를 찾는 함수
from collections import Counter

def largestana(str1):
    # 공백으로 구분된 입력 문자열을 단어로 분리
    str1 = str1.split(" ")
    # 주어진 문자열 목록에서 각 단어를 정렬
    for i in range(0, len(str1)):
        str1[i] = ''.join(sorted(str1[i]))
    # Counter 메서드로 딕셔너리 생성
    # (문자열이 키, 빈도수가 값)
    newstr1 = Counter(str1)
    # max 함수로 빈도수의 최댓값 출력
    print("가장 큰 애너그램 부분 집합의 크기 ::>", max(newstr1.values()))

# 드라이버 프로그램
if __name__ == "__main__":
    str1 = input("문자열을 입력하세요 ::>")
    largestana(str1)

실행 결과

문자열을 입력하세요 ::>qwe ewq rty ytr ytr ytr
가장 큰 애너그램 부분 집합의 크기 ::> 4

코드 동작 원리

입력 "qwe ewq rty ytr ytr ytr"를 예로 들어 살펴보겠습니다. 각 단어를 글자순으로 정렬하면 다음과 같습니다.

'qwe', 'ewq' → 정렬 결과 'eqw' (2개)
'rty' → 정렬 결과 'rty' (1개)
'ytr', 'ytr', 'ytr' → 정렬 결과 'rty' (3개)

정렬 후 'rty'가 총 4번('rty' 1번 + 'ytr' 3번) 등장하므로, 가장 큰 애너그램 부분 집합의 크기는 4가 됩니다. 이처럼 정렬과 Counter를 조합하면 별도의 복잡한 비교 로직 없이도 애너그램 그룹의 최대 크기를 손쉽게 계산할 수 있습니다.