- 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.
1. 모든 윈도우 크기를 브루트 포스로 탐색 (타임 아웃)
class Solution:
def minWindow(self, s: str, t: str) -> str:
def contains(s_substr_lst: List, t_lst: List):
# 슬라이딩 윈도우 내에 있으면 제거 후, True 리턴
for t_elem in t_lst:
if t_elem in s_substr_lst:
s_substr_lst.remove(t_elem)
else:
return False
return True
if not s or not t:
return ''
window_size = len(t)
#range는 그 전 범위까지만 찾으므로 + 1
# 여기서는 window_size가 t를 시작으로 한칸씩 증가 (최대 s의 길이)
for size in range(window_size, len(s) + 1):
for left in range(len(s) - size + 1):
s_substr = s[left:left + size]
if contains(list(s_substr), list(t)):
return s_substr
return ''
-
최소 윈도우라고 했으니 일단
T의 크기부터 시작해 점점 크기를 키워가며 모든 위도우 크기에 대해 다음고 같이 탐색을 시도해볼 수 있겠다.
-
예제에서
T는 3개의 문자이므로 먼저 슬라이딩 윈도우 사이즈를3으로 하고, 끝까지 스캔한 다음,T에 해당하는 문자열을 발견하지 못한 경우4, 다시5,6... 으로 크기를 늘리는 방법을 고민할 수 있다.- 이렇게 하면
T문자열을 가장 먼저 찾게 되는 윈도우 사이즈가 정답이 된다.
- 이렇게 하면
-
그러나, 이 문제에는 시간 복잡도 O(n) 제한이 있다.
- 이 풀이의 경우 O(n2)이므로 이렇게 풀이해선 안 되며, 실제로 이렇게 구현해본 다음의 코드는 타임아웃으로 풀리지 않았다.
-
contains()함수에서t의 문자를 하나씩 비교하며 슬라이딩 윈도우 내에 속한 문자를 제거하는 방식으로 포함 여부를 판단했다.- 이미 제거되었거나 등의 이뮤로 문자가 없다면
False를 리턴하게 했다.
- 이미 제거되었거나 등의 이뮤로 문자가 없다면
- 문자 단위의 포함 여부를 판별하는 것은 반드시 일대일로 문자가 대응되어야 한다는 점에서, 전체를 한 번에 비교하기 어렵고, 정렬해서 풀이하기도 어렵다.
2. 투 포인터, 슬라이딩 윈도우로 최적화 (108ms)
class Solution:
def minWindow(self, s: str, t: str) -> str:
#{key(아이템 값): value(아이템 개수)}
need = collections.Counter(t)
missing = len(t)
left = start = end = 0
#오른쪽으로 이동
#인덱스 1번부터 시작 enumerate(?, 1)
for right, char in enumerate(s, 1):
missing -= need[char] > 0
need[char] -= 1
#필요 문자가 0이면 왼쪽 포인터 이동 판단
if missing == 0:
while left < right and need[s[left]] < 0:
need[s[left]] += 1
left += 1
if not end or right - left <= end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1
return s[start:end]
-
이런 유형의 문제는 투 포인터를 사용하면 O(n2)에서 O(n)으로 줄일 수 있다.
-
계속 우측으로 이동하는 슬라이딩 윈도우이면서 적절한 위치를 찾았을 때 좌우 포인터의 크기를 좁혀나가는 투 포인터로 풀이할 수 있을 것 같다.
-
-
먼저 기본 변수를 구현해보자.
-
need는 필요한 문자 각각의 개수,missing은 필요한 문자의 전체 개수로 한다.- 즉
missing은t의 개수
- 즉
-
-
오른쪽 포인터인
right값을 계속 늘려 나간다. 슬라이딩 윈도우의 크기가 점점 더 커지는 형태가 된다.-
enumerate(n, 1)은 1부터 시작한다는 의미이다. -
파이썬의 슬라이싱은
s[n:n + 1]의 형태이므로 오른쪽 포인터인right는1부터 시작하게 한다.
-
-
현재 문자가 필요한 문자
need[char]에 포함되어 있다면 필요한 문자인 전체 개수인missing을1감소하고, 해당 문자의 필요한 개수need[char]도1감소한다.
-
missing이0이 되면, 즉 필요한 문자의 개수가0이 된다면 이제 왼쪽 포인터를 더 줄일 수 있는지 살핀다.-
기준은 음수인 경우다. (이부분이 헷갈렸지만,
Counter()모듈은 없는 수일 경우 음수를 반환한다) -
즉 왼쪽 포인터가 불필요한 문자를 가리키고 있다면 분명 음수일 것이고,
0을 가리키는 위치까지 왼쪽 포인터를 이동한다. -
while 조건문은
while left < right and need[s[left]] != 0:으로 해도 동일한 결과가 된다.- 다시 슬라이딩 윈도우의 크기가 점점 더 줄어드는 형태가 된다.
-
-
그렇게
missing이0이 될 때까지의 오른쪽 포인터와,need[s[left]]가0이 될 때까지의 왼쪽 포인터를 정답으로 간주한다.- 이 값은 더 작은 값을 찾을 때까지 유지하다가 가장 작은 값인 경우, 정답으로 슬라이싱 결과를 리턴한다.
3. Counter로 좀 더 편리한 풀이 (1924ms)
class Solution:
def minWindow(self, s: str, t: str) -> str:
t_count = collections.Counter(t)
current_count = collections.Counter()
start = float('-inf')
end = float('inf')
left = 0
#오른쪽 포인터 이동
for right, char in enumerate(s, 1):
current_count[char] += 1
#AND 연산 결과로 왼쪽 포인터 이동 판단
while current_count & t_count == t_count:
if right - left < end - start:
start, end = left, right
current_count[s[left]] -= 1
left += 1
return s[start: end] if end - start <= len(s) else ''
-
필요한 문자의 개수를 직접 계산하지 않고
collections.Counter의 기능을 이용해, 매우 편리하게 풀이해보자. -
같은 방식으로 풀되
missing == 0대신Counter()의 AND 연산으로 좀 더 우아하게 비교해본다.-
지금까지 계산한
current_count와t_count의 AND 연산으로 모든 결과가 포함 되는지 여부를 확인할 수 있다. -
요소가 하나라도 비어있다면 AND 연산 결과는
t_count와 일치하지 않을 것이다.
-
-
아쉽게도 이 풀이는 너무 느리다.
- 아마도
Counter끼리 AND연산으로 비교하는 과정current_count & t_count이 내부적으로 매우 무거운 연산이기 때문으로 추측된다.
- 아마도
