이번 글에서는 아래 문제 상황을 파이썬 코드로 해결하는 방법을 알아보겠습니다.
문제 정의
문제 — 텍스트(text)와 패턴(pattern)이 주어졌을 때, 텍스트 안에서 패턴 자체뿐만 아니라 패턴의 모든 순열(아나그램)이 등장하는 위치를 전부 출력해야 합니다.
예를 들어 패턴이 "TOR"라면 "ROT", "OTR", "ORT"처럼 같은 문자들을 재배열한 문자열 역시 모두 검색 대상에 포함됩니다.
풀이 접근: 슬라이딩 윈도우 + 문자 빈도 배열
모든 부분 문자열을 일일이 정렬해 비교하는 브루트포스 방식은 비효율적입니다. 대신 길이가 M인 슬라이딩 윈도우(sliding window)와 문자별 출현 횟수 배열(count array)을 함께 사용하면 훨씬 효율적으로 해결할 수 있습니다.
알고리즘의 동작 순서는 다음과 같습니다.
- 패턴의 문자 빈도를
countP배열에 저장합니다. - 텍스트의 첫 M개 문자 빈도를
countTW배열에 저장합니다. - 윈도우를 오른쪽으로 한 칸씩 이동하면서, 새로 들어온 문자의 개수는 1 증가시키고 윈도우에서 밀려난 문자의 개수는 1 감소시킵니다.
- 매 이동 후
compare()함수로 두 배열이 완전히 같은지 확인하고, 같다면 해당 시작 인덱스를 출력합니다. - 루프가 종료된 뒤에는 마지막 윈도우를 별도로 검사합니다.
두 빈도 배열이 일치한다는 것은 현재 윈도우의 문자 구성이 패턴과 정확히 같다는 의미이며, 곧 그 위치에 패턴 또는 그 아나그램이 존재함을 뜻합니다.
구현 예제
# 최대 문자 값
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("It is Found at Index : ", N-M)
# 메인 실행부
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)
실행 결과
Found at Index 2
"TUTORIALSPOINT"에서 인덱스 2부터 4까지의 부분 문자열은 "TOR"이며, 이는 패턴 그 자체이므로 인덱스 2에서 발견된 것입니다. 만약 텍스트에 "ROT"나 "OTR" 같은 재배열 형태가 포함되어 있었다면 해당 위치 역시 함께 출력됩니다.
위 코드의 모든 변수는 지역 범위(local scope)에서 선언되었으며, 각 변수의 참조 관계는 위 그림에서 확인할 수 있습니다.
복잡도 분석
compare() 함수가 최대 MAX(300)번 반복하므로 전체 시간 복잡도는 O((N−M+1) × MAX)입니다. MAX는 고정 상수이므로 사실상 O(N)에 가깝게 동작합니다. 나아가 현재 일치하는 문자 개수를 실시간으로 추적하는 카운터를 도입하면 매번 배열 전체를 비교하지 않아도 되어 성능을 더욱 개선할 수 있습니다.
마무리
이번 글에서는 파이썬으로 아나그램 부분 문자열 검색 프로그램을 작성하는 방법을 배웠습니다. 슬라이딩 윈도우와 문자 빈도 배열의 조합은 다양한 문자열 검색 문제에서 활용되는 강력한 패턴이므로 꼭 익혀두시기 바랍니다.