두 개의 문자열 s와 t가 주어졌을 때, s 안에서 t의 모든 문자를 포함하는 가장 짧은 부분 문자열(substring)의 길이를 구하는 문제입니다. 만약 그러한 부분 문자열이 존재하지 않는다면 -1을 반환해야 합니다.
예를 들어, s = "thegrumpywizardmakes", t = "wake"라고 입력하면 출력은 10이 됩니다. "w", "a", "k", "e" 네 문자를 모두 포함하는 가장 짧은 구간이 "wizardmake"(길이 10)이기 때문입니다.
해결 접근 방식: 슬라이딩 윈도우
이 문제는 투 포인터 기반의 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- t의 각 문자별 빈도수를 담은 카운터(counter)를 생성합니다.
- 윈도우의 시작 지점(start)을 0으로 초기화합니다.
- 최소 부분 문자열 길이(min_subs)를 무한대(inf)로 초기화합니다.
- rem 변수에 t에 포함된 서로 다른 문자의 개수를 저장합니다.
- end 포인터를 0부터 s의 끝까지 한 칸씩 이동하며 다음을 반복합니다.
- 현재 문자(current)가 카운터에 있다면 해당 문자의 개수를 1 감소시킵니다.
- 감소 후 개수가 0이 되면, 해당 문자의 요구량이 모두 충족된 것이므로 rem을 1 감소시킵니다.
- rem이 0이 되면(모든 문자가 윈도우 안에 들어온 상태), start 포인터를 앞으로 이동시키며 윈도우를 최대한 줄여봅니다.
- start 위치의 문자(prev_char)가 카운터에 있으면 개수를 1 증가시키고, 증가 후 값이 0보다 커지면 해당 문자가 부족해진 것이므로 rem을 1 증가시켜 반복을 종료합니다.
- 각 단계에서 min_subs와 현재 윈도우 크기(end - start + 1) 중 작은 값을 min_subs에 저장합니다.
- 반복이 끝난 후 min_subs가 여전히 무한대라면 조건을 만족하는 부분 문자열이 없으므로 -1을 반환하고, 그렇지 않으면 min_subs를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 위 알고리즘을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, a, b):
counter = {}
for char in b:
counter[char] = counter.get(char, 0) + 1
start = 0
min_subs = float("inf")
rem = len(counter)
for end in range(len(a)):
current = a[end]
if current in counter:
counter[current] -= 1
if counter[current] == 0:
rem -= 1
while rem == 0:
prev_char = a[start]
if prev_char in counter:
counter[prev_char] += 1
if counter[prev_char] > 0:
rem += 1
min_subs = min(min_subs, end - start + 1)
start += 1
return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))
입력
s = "thegrumpywizardmakes", t = "wake"
출력
10
시간 복잡도 분석
end 포인터와 start 포인터는 각각 문자열을 한 번씩만 순회하므로, 전체 시간 복잡도는 O(n)(n은 문자열 s의 길이)입니다. 추가로 사용되는 카운터 딕셔너리의 공간 복잡도는 t에 포함된 서로 다른 문자 수에 비례하여 O(m)(m은 문자열 t의 고유 문자 수)입니다. 브루트포스 방식(O(n²) 이상)에 비해 훨씬 효율적이므로, 실제 코딩 테스트나 면접에서 자주 등장하는 슬라이딩 윈도우 대표 유형의 문제입니다.