문제 소개
두 개의 문자열 s와 t가 주어졌을 때, 문자열 s 안에서 t가 부분 수열(subsequence)로 포함되는 가장 짧은 부분 문자열을 찾아야 합니다. 만약 조건을 만족하는 부분 문자열이 존재하지 않으면 빈 문자열("")을 반환하고, 가장 짧은 후보가 여러 개라면 가장 왼쪽에 있는 것을 선택합니다.
예를 들어 입력이 s = "abcbfbghfb", t = "fg"라면 출력은 fbg가 됩니다. 문자열에서 f(인덱스 4)와 g(인덱스 6) 사이의 "fbg"가 조건을 만족하는 가장 짧은 구간이기 때문입니다.
알고리즘 접근 방식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 t의 문자를 하나씩 늘려 가며, 각 위치에서 "지금까지 처리한 t의 접두사를 부분 수열로 포함하는" 최소 윈도우 길이를 갱신하는 것입니다.
구체적인 단계는 다음과 같습니다.
- N := 문자열 S의 길이
- dp := 크기가 N인 리스트를 무한대(INF)로 초기화
- i를 0부터 N-1까지 반복하며, S[i]가 T[0]과 같으면 dp[i] := 1로 설정
- j를 1부터 len(T)-1까지 반복:
- last := 새로운 딕셔너리(맵)
- dp2 := 크기가 N인 리스트를 무한대로 초기화
- i를 0부터 N-1까지 반복하며, S[i]가 T[j]와 같으면:
- prev_i := last에서 T[j-1]에 해당하는 값 조회
- prev_i가 None이 아니면 dp2[i] := dp[prev_i] + (i - prev_i)
- last[S[i]] := i 기록
- dp := dp2로 교체
- m := dp의 최솟값, i := dp에서 m이 위치한 인덱스
- m이 무한대라면 빈 문자열 반환
- 그렇지 않으면 S[i - dp[i] + 1 : i + 1] 범위의 부분 문자열 반환
핵심 로직 이해하기
- dp 배열의 의미: dp[i]는 "인덱스 i에서 끝나고, 지금까지 처리한 T의 접두사를 부분 수열로 담는 가장 짧은 부분 문자열의 길이"를 나타냅니다.
- last 딕셔너리의 역할: 현재 라운드에서 각 문자가 마지막으로 등장한 인덱스를 저장해 두었다가, 다음 문자를 연결할 때 즉시 참조합니다.
- 길이 계산: 이전 문자 위치 prev_i까지의 최소 길이 dp[prev_i]에 두 위치 사이의 거리 (i - prev_i)를 더하면 새로운 윈도우 길이가 됩니다.
이 알고리즘의 시간 복잡도는 O(len(S) × len(T)), 공간 복잡도는 O(len(S))입니다.
파이썬 구현 예제
class Solution:
def solve(self, S, T):
INF = float("inf")
N = len(S)
dp = [INF] * N
for i in range(N):
if S[i] == T[0]:
dp[i] = 1
for j in range(1, len(T)):
last = {}
dp2 = [INF] * N
for i in range(N):
if S[i] == T[j]:
prev_i = last.get(T[j - 1], None)
if prev_i is not None:
dp2[i] = dp[prev_i] + (i - prev_i)
last[S[i]] = i
dp = dp2
m = min(dp)
i = dp.index(m)
if m == INF:
return ""
return S[i - dp[i] + 1 : i + 1]
ob = Solution()
print(ob.solve("abcbfbghfb", "fg"))
실행 결과
입력:
"abcbfbghfb", "fg"
출력:
fbg
출력 결과 "fbg"는 문자열 s에서 t = "fg"를 부분 수열로 포함하는 가장 짧으면서도 가장 왼쪽에 있는 부분 문자열입니다.