리트코드(leetcode) / 윈도우 알고리즘 / minimum window substring

 

 

https://leetcode.com/problems/minimum-window-substring/

Minimum Window Substring - LeetCode

 

문제 번역

각 m와 n의 길이를 가진 s와 t라는 string이 주어집니다. t가 가진 모든 글자를 포함(중복되는 글자도 고려)하는 s의 부분 문자열 중 가장 작은 값을 구하시오. 해당되는 값이 없다면 빈 문자열을 반환합니다.

 

예시

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

해설: A, B, C 를 포함하는 가장 작은 s의 부분 문자열은 BANC 이다.

 

Input: s = "a", t = "a"
Output: "a"

 

Input: s = "a", t = "aa"
Output: ""

해설: a, a 를 포함하는 가장 작은 s의 부분 문자열이 없으므로 빈 문자열을 반환한다.

 

나의 풀이

요약

슬라이딩 윈도우 알고리즘 문제입니다.

s를 처음부터 끝까지 돌며 t가 가진 모든 글자를 포함한 윈도우를 유효한 윈도우로 지정합니다. 유효한 윈도우 중 가장 작은 크기의 윈도우를 구합니다.

 

 

상세

우선 두 개의 Counter 객체를 생성합니다.

하나는 t 문자열에 관한 카운터 (t 문자열 중 어떤 글자가 더 필요한지 알아보기 위한 용도),

하나는 현재 window에 해당하는 부분 문자열에 대한 카운터입니다.

따라서 각각 Counter(t), 빈 카운터로 시작합니다.

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        
        # if t = 'ABC'
        # required_counter would be {A:1,B:1,C:1}
        # window_counter would be {}
        
        # if t = 'aa'
        # required_counter would be {a:2}

 

 

그리고 포인터를 선언해줍니다.

슬라이딩 윈도우 기법으로 탐색해야 하기에 투 포인터를 활용합니다. 두 포인터 모두 0번 인덱스에서 시작하도록 합니다.

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        pointer_left = pointer_right = 0

 

유효한 윈도우를 찾았을 때 해당 위치도 기억하고 있어야 하므로 window_left, window_right이라는 추가적인 포인터도 선언합니다.

저는 그냥 undefined 상태로 선언만 해두었습니다.

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        pointer_left = pointer_right = 0
        window_left = window_right = None

 

required_length라는 t의 길이를 값으로 가진 추가적인 변수도 생성합니다.

t에 해당하는 글자를 하나씩 찾을때마다 -1 해줄 예정입니다. 그러면 0이 된다면 조건을 충족했다는 뜻이 될 것이며,

일종의 for문 break용 플래그로 쓰일 수 있을 겁니다.

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        
        pointer_left = pointer_right = 0
        window_left = window_right = None
        
        required_length = len(t)

 

이제 이중 for문을 만들어줍니다.

밖에 있는 for문은 pointer_left가 s 문자열의 범위를 벗어나지 않도록 하고, (여기 빠져나가면 탐색 종료)

안쪽에 있는 for문은 pointer_right가 t 문자열에 포함된 글자를 모두 찾거나, 마찬가지로 s 문자열의 범위를 벗어날 때까지 돕니다.

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        
        pointer_left = pointer_right = 0
        window_left = window_right = None

        required_length = len(t)

        while pointer_left < len(s):
            while required_length != 0 and pointer_right < len(s):

 

우 포인터 for문 로직

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        
        pointer_left = pointer_right = 0
        window_left = window_right = None

        required_length = len(t)

        while pointer_left < len(s):

            while required_length != 0 and pointer_right < len(s):
                right_char = s[pointer_right]
                window_counter[right_char] += 1
                # 👆🏻 현재 우 포인터 위치에 놓인 글자를 윈도우에 추가

                if required_counter[right_char] >= window_counter[right_char]:
                    required_length -= 1
                # 👆🏻 현재 글자가 조건을 충족하기 위해 더 필요한 글자라면 required_length - 1

                pointer_right += 1
                # 👆🏻 우 포인터 우측으로 한 칸 이동

 

좌 포인터 for문 로직

from collections import Counter


class Solution:

    """
    # EXAMPLE
    # s = 'AD0BEC0DEBANC'
    # t = 'ABC'
    # should return 'BANC'
    """

    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()

        pointer_left = pointer_right = 0
        window_left = window_right = None

        required_length = len(t)

        while pointer_left < len(s):

            while required_length != 0 and pointer_right < len(s):
                right_char = s[pointer_right]
                window_counter[right_char] += 1

                if required_counter[right_char] >= window_counter[right_char]:
                    required_length -= 1

                pointer_right += 1

            left_char = s[pointer_left]

            if required_length == 0:
            # 👆🏻 필요한 글자수롤 모두 채웠다면 
                if window_left is None or window_right - window_left > pointer_right - pointer_left:
                    window_left, window_right = pointer_left, pointer_right
                # 👆🏻 지금 기억하고 있는 가장 작은 윈도우 사이즈보다 현재 좌우포인터 간격이 더 작다면 재할당

            window_counter[left_char] -= 1
            # 👆🏻 윈도우에서 현재 좌 포인터에 해당하는 글자 제거
            
            if required_counter[left_char] > window_counter[left_char]:
                required_length += 1
            # 👆🏻 좌 포인터의 글자를 지우고 보니 요구 조건 충족이 안된다면, required_length 1 추가

            pointer_left += 1 # 좌 포인터 한 칸 이동

 

전체 코드

from collections import Counter


class Solution:

    """
    # EXAMPLE
    # s = 'AD0BEC0DEBANC'
    # t = 'ABC'
    # should return 'BANC'
    """

    def minWindow(self, s: str, t: str) -> str:
        required_counter, window_counter = Counter(t), Counter()
        
        pointer_left = pointer_right = 0
        window_left = window_right = None

        required_length = len(t)

        while pointer_left < len(s):

            while required_length != 0 and pointer_right < len(s):
                right_char = s[pointer_right]
                window_counter[right_char] += 1

                if required_counter[right_char] >= window_counter[right_char]:
                    required_length -= 1

                pointer_right += 1

            left_char = s[pointer_left]

            if required_length == 0:
                if window_left is None or window_right - window_left > pointer_right - pointer_left:
                    window_left, window_right = pointer_left, pointer_right

            window_counter[left_char] -= 1

            if required_counter[left_char] > window_counter[left_char]:
                required_length += 1

            pointer_left += 1

        return s[window_left:window_right] if window_left is not None else ''

 

 

 

 

그나저나 문제에 나오는 인수 이름 진짜 그지같은듯..... s, t가 뭐냐 s, t가...............