파이썬으로 애너그램 단어 중 가장 큰 부분 집합의 크기 찾기

문제 소개

공백으로 구분된 여러 개의 소문자 단어가 주어졌을 때, 서로 애너그램 관계에 있는 단어들만 모아 만들 수 있는 가장 큰 부분 집합의 크기를 구하는 것이 이번 과제입니다.

여기서 애너그램(anagram)이란 한 문자열의 글자들을 재배열하여 다른 문자열을 만들 수 있는 관계를 의미합니다. 예를 들어 'python'과 'typhon'은 같은 글자들로 이루어져 있으므로 서로 애너그램입니다.

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

알고리즘

1단계: 공백으로 구분된 입력 문자열을 단어 단위로 분리한다.
2단계: 문자열 목록에 있는 각 단어를 알파벳 순으로 정렬한다.
3단계: Counter 메서드를 사용해 딕셔너리를 만든다. 이때 정렬된 문자열이 키(key), 등장 빈도가 값(value)이 된다.
4단계: max 함수를 사용해 빈도 값의 최댓값을 구한다.

동작 원리

각 단어를 글자순으로 정렬하면 애너그램 관계인 단어들은 모두 동일한 문자열로 변환됩니다. 예를 들어 'qwe'와 'ewq'는 정렬하면 둘 다 'eqw'가 됩니다. 따라서 정렬된 문자열별로 등장 횟수를 세면, 가장 많이 등장하는 그룹의 크기가 곧 가장 큰 애너그램 부분 집합의 크기가 됩니다.

예제 코드

# 애너그램 단어로 이루어진 가장 큰 부분 집합의 크기를 찾는 함수
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'는 정렬 후 'eqw'로 묶이고, 'rty'와 세 번 입력된 'ytr'은 모두 'rty'로 묶입니다. 따라서 'rty' 그룹에 속하는 단어가 총 4개로 가장 많으며, 실행 결과도 4가 출력됩니다.