문제 정의
두 개의 문자열 S와 T가 주어졌을 때, T가 부분 수열(subsequence)이 되도록 하는 S의 최소 길이 부분 문자열(윈도우) W를 찾는 문제입니다. 만약 S 안에서 T의 모든 문자를 순서대로 포함하는 윈도우가 존재하지 않는다면 빈 문자열을 반환해야 하고, 조건을 만족하는 윈도우가 여러 개라면 그중 시작 인덱스가 가장 왼쪽에 있는 것을 반환해야 합니다.
예를 들어 입력이 S = "abcdebdde", T = "bde"라고 가정해 보겠습니다. 이 경우 출력은 "bcde"가 됩니다. "bcde"가 "bdde"보다 먼저 등장하기 때문입니다. 반면 "deb"처럼 문자들이 포함되어 있어도 정답이 될 수 없는데, 윈도우 내부에서 T의 문자들은 반드시 주어진 순서 그대로 나타나야 하기 때문입니다.
풀이 접근 방식
이 문제는 순방향 탐색과 역방향 추적을 결합한 두 포인터 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 왼쪽에서 오른쪽으로 S를 순회하면서 T의 문자를 하나씩 매칭합니다(tidx 포인터 사용).
- T의 마지막 문자까지 매칭에 성공하면, 해당 위치에서 다시 뒤로 되돌아가며 이 윈도우가 시작될 수 있는 가장 왼쪽 지점을 찾습니다.
- 발견되는 윈도우마다 길이를 비교하여 최솟값과 시작 위치를 갱신합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 초기화: tidx := 0, tlen := T의 길이, n := S의 길이, i := 0, length := 무한대(INT_MAX), start := -1로 설정합니다.
- 순방향 탐색: i < n인 동안 반복하며, S[i]가 T[tidx]와 같으면 tidx를 1 증가시킵니다.
- 윈도우 완성 확인: tidx가 tlen에 도달하면 T 전체가 매칭된 것이므로 end := i + 1로 윈도우의 끝 위치를 기록합니다.
- 역방향 추적: tidx를 하나 감소시킨 뒤, tidx ≥ 0인 동안 i를 거꾸로 이동하며 S[i]와 T[tidx]가 일치할 때마다 tidx를 감소시킵니다. 루프가 종료되면 i는 윈도우의 시작 지점 바로 앞에 위치하게 됩니다.
- 위치 복원 및 갱신: i와 tidx를 각각 1씩 증가시켜 원래 탐색 지점으로 복원한 후, end − i가 현재 length보다 작으면 length := end − i, start := i로 갱신합니다.
- 결과 생성: 모든 탐색이 끝난 후 start가 -1이 아니라면 S[start]부터 length 길이만큼의 문자를 이어 붙여 ret을 만들어 반환합니다.
C++ 구현 예제
다음 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string S, string T) {
int tidx = 0;
int tlen = T.size();
int n = S.size();
int i = 0;
int length = INT_MAX;
int start = -1;
string ret;
while (i < n) {
if (S[i] == T[tidx]) {
tidx++;
if (tidx == tlen) {
int end = i + 1;
tidx--;
while (tidx >= 0) {
if (S[i] == T[tidx]) {
tidx--;
}
i--;
}
i++;
tidx++;
if (end - i < length) {
length = end - i;
start = i;
}
}
}
i++;
}
if (start != -1)
for (int i = start; i < start + length; i++)
ret += S[i];
return ret;
}
};
main(){
Solution ob;
cout << (ob.minWindow("abcdebdde", "bde"));
}
입력
"abcdebdde", "bde"
출력
"bcde"
복잡도 분석
순방향 탐색에는 O(n)의 시간이 걸리며, T 전체가 매칭될 때마다 수행되는 역방향 추적은 최대 O(m)(m은 T의 길이)만큼 진행됩니다. 따라서 최악의 경우 전체 시간 복잡도는 O(n × m)이지만, 실제로는 역방향 추적이 발견된 윈도우의 길이만큼만 수행되므로 대부분 훨씬 빠르게 동작합니다. 공간 복잡도는 결과 문자열을 제외하면 O(1)입니다.