개요
이 글에서는 파이썬을 활용해 애너그램 부분 문자열 검색(Anagram Substring Search) 문제를 해결하는 방법을 알아봅니다.
문제 정의
주어진 텍스트(text)와 패턴(pattern)이 있을 때, 텍스트 안에서 패턴 자체뿐만 아니라 패턴의 모든 순열(애너그램)이 나타나는 위치를 모두 찾아 출력하는 것이 목표입니다.
예를 들어 텍스트가 "TUTORIALSPOINT"이고 패턴이 "TOR"라면, "ROT", "OTR"처럼 같은 문자들로 재배열된 형태도 모두 검색 대상이 됩니다.
해결 접근 방식
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 빈도수 카운팅을 조합하면 효율적으로 해결할 수 있습니다.
- 패턴에 포함된 각 문자의 개수를 countP 배열에 저장합니다.
- 텍스트에서 패턴과 같은 길이의 첫 번째 윈도우에 대한 문자 개수를 countTW 배열에 저장합니다.
- 윈도우를 한 칸씩 오른쪽으로 이동하면서, 새로 들어온 문자는 1 증가시키고 윈도우에서 벗어난 문자는 1 감소시킵니다.
- 매 단계마다 두 배열을 비교하여 완전히 일치하면 현재 위치에서 패턴의 애너그램이 존재한다는 의미이므로 시작 인덱스를 출력합니다.
두 배열의 크기는 ASCII 문자 집합을 충분히 커버할 수 있도록 300으로 설정했습니다.
구현 예제
# 최대 문자 코드 값
MAX = 300
# 두 빈도수 배열이 동일한지 비교
def compare(arr1, arr2):
for i in range(MAX):
if arr1[i] != arr2[i]:
return False
return True
# 애너그램 검색 함수
def search(pat, txt):
M = len(pat)
N = len(txt)
# countP: 패턴의 문자 빈도수
# countTW: 현재 텍스트 윈도우의 문자 빈도수
countP = [0] * MAX
countTW = [0] * MAX
# 초기 윈도우와 패턴의 빈도수 계산
for i in range(M):
countP[ord(pat[i])] += 1
countTW[ord(txt[i])] += 1
# 슬라이딩 윈도우 탐색
for i in range(M, N):
# 현재 윈도우와 패턴의 빈도수 비교
if compare(countP, countTW):
print("Found at Index", (i - M))
# 윈도우에 새 문자 추가
countTW[ord(txt[i])] += 1
# 윈도우에서 벗어난 문자 제거
countTW[ord(txt[i - M])] -= 1
# 마지막 윈도우 확인
if compare(countP, countTW):
print("Found at Index", (N - M))
# 실행
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)실행 결과
Found at Index 2"TUTORIALSPOINT"에서 인덱스 2부터 시작하는 부분 문자열은 "TOR"로, 패턴과 정확히 일치하므로 해당 위치가 출력됩니다.
동작 원리 살펴보기
처음에는 텍스트의 앞 세 글자 "TUT"에 대한 빈도수(T: 2, U: 1)가 countTW에 저장됩니다. 이후 루프가 진행되면서 윈도우가 한 칸씩 이동하고, 윈도우가 "TOR" 구간에 도달하는 순간 countP와 countTW가 완전히 일치하게 되어 인덱스 2가 출력됩니다.
모든 변수는 지역 스코프(local scope) 내에서 선언되며, 함수 호출이 진행되는 동안에만 유효합니다.
시간 복잡도
compare 함수는 배열 전체(최대 300칸)를 순회하므로 O(MAX) 시간이 걸리고, 이 비교가 텍스트의 각 위치마다 수행되므로 전체 시간 복잡도는 O(N × MAX)입니다. 여기서 N은 텍스트의 길이입니다. 공간 복잡도는 고정 크기 배열 두 개만 사용하므로 O(MAX)입니다.
마무리
이번 글에서는 파이썬으로 애너그램 부분 문자열 검색 프로그램을 구현하는 방법을 배웠습니다. 슬라이딩 윈도우와 빈도수 비교만으로도 패턴의 모든 순열을 효율적으로 찾을 수 있다는 점이 핵심입니다.