파이썬에서 리스트와 딕셔너리를 활용해 아나그램 찾아 함께 출력하기

이 튜토리얼에서는 파이썬의 리스트(list)와 딕셔너리(dictionary)를 활용해 문자열 목록 속에서 서로 아나그램 관계인 단어들을 찾아 한데 모아 출력하는 프로그램을 작성해 보겠습니다. 아나그램(anagram)이란 같은 문자들로 구성되어 있지만 순서만 다른 단어를 의미합니다. 예를 들어 'peach'와 'cheap'은 동일한 알파벳으로 이루어진 아나그램입니다.

문제 해결에는 여러 가지 접근 방식이 있을 수 있습니다. 튜토리얼을 따라가기 전에 먼저 스스로 코드를 작성해 보는 것을 권장합니다. 아이디어가 떠오르지 않는다면 아래 단계를 차례대로 따라 해 보세요.

알고리즘

1. 문자열 리스트를 초기화한다.
2. 빈 딕셔너리를 초기화한다.
3. 문자열 리스트를 순회한다.
   3.1. 문자열을 정렬한 값을 키로 삼아, 딕셔너리에 존재하는지 확인한다.
      3.1.1. 키가 이미 존재하면 원본 문자열을 해당 키의 리스트에 추가한다.
   3.2. 키가 존재하지 않으면 정렬된 문자열을 키로 하는 빈 리스트를 만들고 원본 문자열을 추가한다.
4. 결과를 담을 빈 문자열을 초기화한다.
5. 딕셔너리의 모든 항목을 순회하며 값을 하나의 문자열로 합친다.
6. 최종 문자열을 출력한다.

핵심 아이디어는 간단합니다. 두 문자열을 각각 정렬했을 때 결과가 같다면 두 문자열은 아나그램 관계라는 점을 이용하는 것입니다. 정렬된 문자열을 딕셔너리의 키로 사용하면, 같은 그룹에 속한 단어들을 하나의 리스트로 깔끔하게 묶을 수 있습니다.

예제 코드

## 문자열 리스트 초기화
strings = ["apple", "orange", "grapes", "pear", "peach", "cheap"]
## 빈 딕셔너리 초기화
anagrams = {}
## 문자열 리스트 순회
for string in strings:
    ## 문자열을 정렬해 키 생성
    key = "".join(sorted(string))
    ## 키가 딕셔너리에 이미 존재하는지 확인
    if key in anagrams.keys():
        ## 원본 문자열을 해당 키의 리스트에 추가
        anagrams[key].append(string)
    else:
        ## 새 키에 빈 리스트를 매핑한 뒤 문자열 추가
        anagrams[key] = []
        anagrams[key].append(string)
## 결과를 담을 빈 문자열 초기화
result = ""
## 딕셔너리 항목 순회
for key, value in anagrams.items():
    ## 각 그룹의 단어를 공백으로 구분해 결과에 추가
    result += " ".join(value) + " "
## 결과 출력
print(result)

예제에는 'peach'와 'cheap'처럼 실제 아나그램 관계인 단어 쌍을 포함시켰습니다. 두 단어는 정렬하면 모두 'acehp'가 되므로 같은 키로 묶이게 됩니다. 참고로 키 존재 여부를 검사할 때는 반드시 정렬된 값인 key를 기준으로 확인해야 하며, 원본 문자열인 string을 기준으로 검사하면 아나그램 그룹화가 올바르게 동작하지 않으니 주의하세요.

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

apple orange grapes pear peach cheap

'peach'와 'cheap'이 나란히 출력된 것을 확인할 수 있습니다. 각 단어는 자신과 같은 아나그램 그룹에 속한 단어들과 함께 배치됩니다.

더 간결하게 작성하기: defaultdict 활용

키 존재 여부를 매번 검사하는 대신, collections 모듈의 defaultdict를 사용하면 코드를 훨씬 간결하게 만들 수 있습니다.

from collections import defaultdict

strings = ["apple", "orange", "grapes", "pear", "peach", "cheap"]
anagrams = defaultdict(list)

for string in strings:
    anagrams["".join(sorted(string))].append(string)

for group in anagrams.values():
    print(" ".join(group))

defaultdict(list)는 존재하지 않는 키에 접근할 때 자동으로 빈 리스트를 생성해 주므로, 조건 분기 없이 곧바로 append()를 호출할 수 있습니다.

시간 복잡도

길이가 k인 문자열 n개가 있다면, 각 문자열을 정렬하는 데 O(k log k)가 걸리고 이를 n번 반복하므로 전체 시간 복잡도는 O(n · k log k)입니다. 일반적인 단어 수준의 짧은 문자열에서는 사실상 O(n)에 가깝게 동작하므로 충분히 효율적입니다.

마무리

이번 튜토리얼에서는 정렬된 문자열을 딕셔너리 키로 활용해 아나그램을 그룹화하고 출력하는 방법을 알아보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.