이 튜토리얼에서는 주어진 문자열 안에서 특정 단어의 아나그램(anagram)이 되는 모든 부분 문자열을 검색하는 프로그램을 작성해 보겠습니다.
아나그램이란 같은 문자들로 구성되어 있지만 순서가 다른 단어를 의미합니다. 예를 들어 'cat'과 'act'는 서로 아나그램 관계입니다.
먼저 예제를 살펴보겠습니다.
입력: anagram = "cat" string = "tacghactcat" 출력: Anagram at 0 Anagram at 5 Anagram at 7 Anagram at 8
위 예제에서 입력 문자열 'tacghactcat' 내부에는 'cat'의 아나그램이 네 곳에 존재하며, 각각의 시작 인덱스를 출력하는 것이 목표입니다.
알고리즘
코드를 작성하기 전에 전체적인 흐름을 단계별로 정리해 보겠습니다.
1. 두 개의 문자열을 초기화합니다.
2. 두 문자열이 서로 아나그램인지 판별하는 함수를 생성합니다.
3. 검색 대상인 메인 문자열을 순회합니다.
3.1. 정의한 함수를 사용해 현재 부분 문자열이 아나그램인지 확인합니다.
3.1.1. True라면 시작 인덱스를 출력합니다.구현 예제
아나그램 여부를 판별할 때는 파이썬의 collections.Counter를 활용하면 편리합니다. Counter는 문자열 내 각 문자의 등장 횟수를 딕셔너리 형태로 저장해 주기 때문에, 두 Counter 객체가 같다면 두 문자열은 동일한 문자를 동일한 개수만큼 포함하고 있다는 뜻, 즉 아나그램 관계임을 알 수 있습니다.
# 아나그램 판별을 위해 collections 모듈 임포트
import collections
# 두 문자열 초기화
anagram = 'cat'
string = 'tacghactcat'
# 아나그램 여부를 확인하는 함수
def is_anagram(string):
# 아나그램인지 검사
if collections.Counter(anagram) == collections.Counter(string):
# 아나그램이면 True 반환
return True
else:
# 아니면 False 반환
return False
# 두 문자열의 길이 계산
anagram_len = len(anagram)
string_len = len(string)
# 메인 문자열을 순회하며 검색
for i in range(string_len - anagram_len + 1):
# 부분 문자열이 아나그램인지 확인
if is_anagram(string[i:i+anagram_len]):
# 시작 인덱스 출력
print(f'Anagram at {i}')실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Anagram at 0 Anagram at 5 Anagram at 7 Anagram at 8
코드 설명 및 성능 개선 팁
루프 범위가 string_len - anagram_len + 1로 설정된 이유는, 마지막 부분 문자열도 검사 범위에 포함시키기 위함입니다. 예를 들어 길이가 12인 문자열에서 길이 3인 아나그램을 찾는다면 시작 인덱스는 최대 9까지 가능합니다.
다만 위 코드는 매번 새로운 Counter 객체를 생성하기 때문에 문자열이 길어질 경우 비효율적일 수 있습니다. 성능을 개선하려면 슬라이딩 윈도우(sliding window) 기법을 적용해, 이전 부분 문자열의 문자 빈도에서 앞 문자 하나를 빼고 뒤에 새로 들어오는 문자 하나를 더하는 방식으로 Counter를 갱신하면 됩니다. 이렇게 하면 시간 복잡도를 크게 줄일 수 있습니다.
마무리
이번 튜토리얼에서는 collections.Counter를 활용해 문자열 내 모든 아나그램 위치를 찾는 방법을 알아보았습니다. 코드와 관련해 궁금한 점이 있다면 댓글로 남겨주세요.