76. Minimum Window Substring

아현·2021년 5월 28일
0

Algorithm

목록 보기
76/400
post-custom-banner

리트코드


  • 문자열 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은 필요한 문자의 전체 개수로 한다.

      • missingt의 개수

  • 오른쪽 포인터인 right 값을 계속 늘려 나간다. 슬라이딩 윈도우의 크기가 점점 더 커지는 형태가 된다.

    • enumerate(n, 1)은 1부터 시작한다는 의미이다.

    • 파이썬의 슬라이싱은 s[n:n + 1]의 형태이므로 오른쪽 포인터인 right1부터 시작하게 한다.

  • 현재 문자가 필요한 문자 need[char]에 포함되어 있다면 필요한 문자인 전체 개수인 missing1 감소하고, 해당 문자의 필요한 개수 need[char]1 감소한다.


  • missing0이 되면, 즉 필요한 문자의 개수가 0이 된다면 이제 왼쪽 포인터를 더 줄일 수 있는지 살핀다.

    • 기준은 음수인 경우다. (이부분이 헷갈렸지만, Counter() 모듈은 없는 수일 경우 음수를 반환한다)

    • 즉 왼쪽 포인터가 불필요한 문자를 가리키고 있다면 분명 음수일 것이고, 0을 가리키는 위치까지 왼쪽 포인터를 이동한다.

    • while 조건문은 while left < right and need[s[left]] != 0:으로 해도 동일한 결과가 된다.

      • 다시 슬라이딩 윈도우의 크기가 점점 더 줄어드는 형태가 된다.

  • 그렇게 missing0이 될 때까지의 오른쪽 포인터와, 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_countt_count의 AND 연산으로 모든 결과가 포함 되는지 여부를 확인할 수 있다.

    • 요소가 하나라도 비어있다면 AND 연산 결과는 t_count와 일치하지 않을 것이다.


  • 아쉽게도 이 풀이는 너무 느리다.

    • 아마도 Counter끼리 AND연산으로 비교하는 과정 current_count & t_count이 내부적으로 매우 무거운 연산이기 때문으로 추측된다.



profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글