C++로 문자열 내 모든 아나그램 시작 인덱스 찾는 방법

문제 개요

문자열 s와 비어 있지 않은 문자열 p가 주어졌을 때, s 안에서 p의 아나그램(anagram)이 시작되는 모든 인덱스를 찾아야 합니다. 두 문자열은 소문자 알파벳으로만 구성되며, s의 길이는 최대 20,000, p의 길이는 최대 100으로 가정합니다.

예를 들어 s가 "cbaebabacd"이고 p가 "abc"라면 출력은 [0, 6]이 됩니다. 인덱스 0에서 시작하는 부분 문자열은 "cba", 인덱스 6에서 시작하는 부분 문자열은 "bac"로, 둘 다 "abc"의 아나그램이기 때문입니다.

해결 전략: 슬라이딩 윈도우와 문자 빈도 카운팅

이 문제는 슬라이딩 윈도우(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 감소시킨 후 루프를 종료합니다.
    • 루프 종료 후 m에 s[left]가 존재하지 않는다면 left := right + 1로 설정합니다.
• 모든 순회가 끝나면 ans를 반환합니다.

이 방식은 각 문자를 최대 두 번(왼쪽 포인터와 오른쪽 포인터)만 방문하므로 시간 복잡도는 O(n)에 가깝게 유지됩니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#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("cbaebabacd", "abc")) ;
}

입력

"cbaebabacd"
"abc"

출력

[0, 6]

정리

이 알고리즘은 p의 문자 빈도를 미리 계산해 둔 뒤, s를 한 번 순회하면서 윈도우를 확장·축소하는 방식으로 동작합니다. 불필요한 재정렬이나 완전 탐색 없이도 모든 아나그램 시작 위치를 O(n) 시간에 찾을 수 있다는 점이 큰 장점입니다. 슬라이딩 윈도우 기법은 문자열 매칭 문제에서 자주 활용되므로, 이 예제를 통해 패턴을 익혀두면 다양한 변형 문제에도 응용할 수 있습니다.