문제
문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.
입력 : S = "AD0BEC0DEBANC", T = "ABC"
출력 : "BANC"
코드
"""
fixme. https://leetcode.com/problems/minimum-window-substring/
fixme. Q76. 부분 문자열이 포함된 최소 윈도우
fixme. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.
fixme. 입력 : S = "AD0BEC0DEBANC", T = "ABC"
fixme. 출력 : "BANC"
"""
import collections
class Solution:
def minWindowPointer(self, s: str, t: str) -> str:
need = collections.Counter(t)
missing = len(t)
left = start = end = 0
# 오른쪽 포인터 이동
for right, char in enumerate(s, 1):
missing -= need[char] > 0
print(need[char])
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]
def minWindowCounter(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 '' 풀이
투포인터(슬라이딩 윈도우)
이런 유형의 문제는 브루트 포스로 풀면 O(N^2)이지만, 투 포인터를 사용하면 O(n)으로 줄일 수 있다. 먼저 다음과 같이 기본 변수를 정의해보자.
need = collections.Counter(t)
missing = len(t)need는 포함해야 할 문자 각각의 개수, missing은 포함해야 할 문자의 전체 개수로 한다. 예제에서 t는 "ABC"이므로 need는 A 1개, B 1개, C 1개이고, missing은 3이다.
for right, char in enumerate(s, 1):
missing -= need[char] > 0
need[char] -= 1
...
...이제 오른쪽 포인터인 right 값을 계속 늘려 나간다. 슬라이딩 윈도우의 크기가 점점 더 커지는 형태가 된다. enumerate() 기본 0부터 시작하지만 enumerate(s, 1)로 두어 1부터 시작하게 한다. 왜냐하면, 오른쪽을 right값으로 슬라이싱 할때 right-1까지 잘리므로 미리 하나 더해서 시작하기 위함이다. 만약 현재 문자가 필요한 문자 need[char]에 포함되어 있다면 필요한 문자의 전체 개수인 missing을 1 감소하고, 해당 문자의 필요한 개수 need[char]도 1 감소한다. 즉 for문이 s를 돌 때 처음 A에서 need[A] = 1이므로 missing 3에서 1을 빼서 missing은 2가되고, need[A]도 하나 빠져서 0이된다. 이렇게 쭉 for문을 돌면 missing이 0이 될 때 right 포인터의 지점이 문자 A, B, C를 전부 포함하고 있는 문자열을 가지게 된다.
if missing == 0:
while left < right and need[s[left]] < 0:
need[s[left]] += 1
left += 1missing이 0이 되면, 즉 필요한 문자의 개수가 0이 된다면 이제 왼쪽 포인터를 더 줄일 수 있는지 살핀다. 기준은 음수인 경우다. 즉 왼쪽 포인터가 불필요한 문자를 가리키고 있다면 이전에 for문에서 need[char] -= 1로 인해 0에서 1씩 마이너스 됨으로써 음수일 것이고, 0을 가리키는 위치까지 왼쪽 포인터를 이동한다. 다시 슬라이딩 윈도우의 크기가 점점 더 줄어드는 형태가 된다.
if missing == 0:
...
...
...
if not end or right - left <= end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1다음 start, end에 지금의 왼쪽, 오른쪽 포인터(left, right)를 저장해둔 뒤 왼쪽 포인터만 살짝 한칸 오른쪽으로 옮기고, 옮긴거에 맞게 need의 해당 문자에 +1, missing +1, left +1을 해주고 더 작은 윈도우가 있는지 for문을 끝까지 돌면서 탐색한다 없으면 저장된 start, end로 슬라이싱해서 반환하면 된다.
Counter로 좀 더 편리하게
missing == 0 대신 Counter()의 AND 연산으로 좀 더 우아하게 비교한다.
t_count = collections.Counter(t)
...
for right, char in enumerate(s, 1):
current_count[char] += 1
while current_count & t_count == t_count:
...이렇게 지금까지 계산한 current_count와 t_current의 AND 연산으로 모든 결과가 포함되는지 여부를 확인할 수 있다. 만약 요소가 하나라도 비어 있다면 AND 연산 결과는 t_count와 일치하지 않을 것이다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]