C++로 최소 윈도우 부분 문자열 구하기: 슬라이딩 윈도우 알고리즘 완벽 정리

문자열 S와 T가 주어졌을 때, S 안에서 T의 모든 문자를 포함하는 최소 길이의 윈도우(부분 문자열)를 찾는 문제입니다. 예를 들어 S = "ABHDAXCVBAGTXATYCB", T = "ABC"라고 한다면, 결과는 "CVBA"가 됩니다.

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 오른쪽 포인터를 확장하며 조건을 만족하는 구간을 찾고, 왼쪽 포인터를 당겨 최소 길이를 유지하는 것입니다.

알고리즘 단계

• 문자 빈도를 저장할 맵 m을 생성하고, x의 각 문자별 빈도를 저장합니다.
• length := s의 크기, left := 0, right := 0, ansLeft := 0, ansRight := 0으로 초기화합니다.
• counter := x의 크기, flag := false, ans := 빈 문자열로 설정합니다.
• right가 s의 끝에 도달할 때까지 다음 과정을 반복합니다.
  • c := s[right]로 현재 문자를 가져옵니다.
  • c가 맵 m에 존재하면, m[c] > 0일 경우 counter를 1 감소시키고 m[c]를 1 감소시킵니다.
  • counter == 0이 되면(필요한 모든 문자를 포함한 상태) left <= right인 동안 내부 반복을 수행합니다.
    • (right - left + 1)이 length 이하이면 length를 갱신하고, flag := true, ansLeft := left, ansRight := right로 저장합니다.
    • left == right이면 내부 루프를 종료합니다.
    • c := s[left]로 왼쪽 문자를 확인하고, c가 m에 존재하면 m[c]를 1 증가시킵니다.
    • m[c] > 0이 되면 counter를 1 증가시킵니다.
    • left를 1 증가시켜 윈도우를 축소합니다.
  • right를 1 증가시켜 윈도우를 확장합니다.
• flag가 false면 조건을 만족하는 윈도우가 없으므로 빈 문자열을 반환합니다.
• 그렇지 않으면 ansLeft부터 ansRight까지의 문자를 이어 붙여 ans를 만들어 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minWindow(string s, string x) {
      map <char, int> m;
      for(int i =0;i<x.size();i++)m[x[i]]++;
      int length = s.size();
      int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
      int counter = x.size();
      bool flag = false;
      string ans = "";
      while(right<s.size()){
         char c = s[right];
         if(m.find(c)!=m.end()){
            if(m[c]>0)counter--;
            m[c]--;
         }
         while(counter == 0 && left<=right){
            if(right-left+1 <=length){
               length = right-left+1;
               flag = true;
               ansLeft = left;
               ansRight = right;
            }
            if(left == right)break;
            c = s[left];
            if(m.find(c)!=m.end()){
               m[c]++;
               if(m[c]>0)counter++;
            }
            left++;
         }
         right++;
      }
      if(!flag)return ans;
      else
      for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

입력

"ABHDAXCVBAGTXATYCB"
"ABC"

출력

CVBA

동작 원리 요약

이 알고리즘은 두 개의 포인터(left, right)를 사용해 윈도우의 크기를 동적으로 조절합니다. 오른쪽 포인터를 이동시키며 필요한 문자를 하나씩 포함하고, 모든 문자가 포함되면(counter == 0) 왼쪽 포인터를 이동시켜 불필요한 부분을 제거합니다. 이 과정에서 발견된 가장 짧은 윈도우의 위치(ansLeft, ansRight)를 기록해 두었다가 마지막에 반환합니다.

시간 복잡도는 O(|S| + |T|)로 각 문자를 최대 두 번씩만 방문하므로 매우 효율적이며, 공간 복잡도는 O(|T|)로 T의 문자 빈도를 저장하는 맵 크기에 비례합니다.