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) 제한이 있다.
contains()
함수에서 t
의 문자를 하나씩 비교하며 슬라이딩 윈도우 내에 속한 문자를 제거하는 방식으로 포함 여부를 판단했다.
False
를 리턴하게 했다.
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
이 될 때까지의 왼쪽 포인터를 정답으로 간주한다.
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
이 내부적으로 매우 무거운 연산이기 때문으로 추측된다.