두 개의 문자열 S와 T가 주어졌을 때, 문자열 T 안에서 S의 아나그램(anagram)이 나타나는 모든 시작 인덱스를 찾아야 합니다. 문자열은 소문자로만 구성되며, S와 T의 길이는 각각 20과 100을 넘지 않는다고 가정합니다.
예를 들어 입력이 S = "cab", T = "bcabxabc"라고 한다면, 출력은 [0, 1, 5]가 됩니다. 이는 부분 문자열 "bca", "cab", "abc"가 각각 인덱스 0, 1, 5에서 시작되는 S의 아나그램이기 때문입니다.
해결 접근 방식
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 빈도수 카운팅을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 맵 m을 정의하고, n := s의 길이, left := 0, right := 0, counter := p의 길이로 초기화합니다.
- 정답을 저장할 배열 ans를 선언합니다.
- p에 포함된 각 문자의 빈도수를 맵 m에 저장합니다.
- right를 0부터 n-1까지 반복합니다.
- m에 s[right]가 존재하고 그 값이 0이 아니라면, m[s[right]]를 1 감소시키고 counter도 1 감소시킵니다. 이때 counter가 0이 되면 현재 left 값을 ans에 추가합니다.
- 그렇지 않은 경우에는 left가 right보다 작은 동안 다음을 반복합니다.
- s[left]가 m에 존재하면 counter를 1 증가시키고 m[s[left]]도 1 증가시킵니다.
- left를 1 증가시킵니다.
- m에 s[right]가 존재하고 값이 0이 아니면 right를 1 감소시킨 후 반복문을 종료합니다.
- 반복이 끝난 후에도 s[left]가 m에 없다면 left := right + 1로 설정합니다.
- 최종적으로 ans를 반환합니다.
구현 예제
아래 코드는 위 알고리즘을 C++로 구현한 것입니다. 동일한 로직은 Python 등 다른 언어로도 손쉽게 옮길 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
map <char, int> m;
int n = s.size();
int left = 0, right = 0;
int counter = p.size();
vector <int> ans;
for(int i = 0; i < p.size(); i++) m[p[i]]++;
for(int right = 0; right < n; right++){
if(m.find(s[right]) != m.end() && m[s[right]]){
m[s[right]]--;
counter--;
if(counter == 0)ans.push_back(left);
} else {
while(left<right){
if(m.find(s[left]) != m.end()) {
counter++;
m[s[left]]++;
}
left++;
if(m.find(s[right]) != m.end() && m[s[right]]){
right--;
break;
}
}
if(m.find(s[left])==m.end())left = right + 1;
}
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.findAnagrams("bcabxabc", "cab")) ;
}입력
"bcabxabc", "cab"
출력
[0, 1, 5]
동작 원리 정리
이 알고리즘은 패턴 문자열 p의 문자 빈도수를 미리 맵에 저장해 둔 뒤, 대상 문자열 s를 왼쪽 포인터(left)와 오른쪽 포인터(right) 두 개로 탐색합니다. 윈도우 내에 p의 문자들이 모두 매칭되어 counter가 0이 되는 순간, 해당 윈도우의 시작 위치인 left를 결과 배열에 기록합니다. 만약 매칭되지 않는 문자를 만나면 윈도우를 앞으로 밀어 불필요한 비교를 건너뛰므로, 전체 시간 복잡도는 O(n) 수준으로 매우 효율적입니다.