슬라이딩 윈도우 (sliding window)

[슬라이딩 윈도우란?]

슬라이딩 윈도우는 윈도우라고 부르는 일정 구간을 단방향으로 이동시켜 가면서 윈도우 안에 있는 데이터를 이용해 주어진 문제를 해결하는 알고리즘이다.

 

슬라이딩 윈도우는 데이터의 정렬여부와 관계없이 사용 가능하다.

 

 

 

---

 

[예제1: 최대 슬라이딩 윈도우 - 구간 내 최댓값 구하기]

배열 nums = [3,  2,  4, -1,  2, -3,  5, -4,  6] 이고 구간(window)의 크기 k = 3이라고 하면

초기에 구간을 가장 왼쪽에 배치하고 이후 한칸씩 오른쪽으로 시프트 해가면서 구간 안에 최댓값을 구해본다.

 

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   4

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   4

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   4

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   2

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   5

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   5

[3,  2,  4, -1,  2, -3,  5, -4,  6]    -->   6

 

따라서 결과는 리스트 [4, 4, 4, 2, 5, 5, 6]가 된다.

 

 

import time
from collections import deque


def get_max_sliding_window(nums: [int], k: int) -> [int]:
    result = []
    window = deque()
    current_max = float('-inf')
    for i, v in enumerate(nums):
        window.append(v)
        # window의 요소가 k개 전일 때는 가장 큰 값을 찾는 것이 무의미 하므로
        # 처음 k개 까지는 window에 넣기만 한다.
        if i < k - 1:
            continue

        # current_max가 최저값이면 새로운 max value를 current_max에 대입한다.
        if current_max == float('-inf'):
            current_max = max(window)
        # 새로 추가되는 값이 기존의 최댓값보다 큰 경우 update
        elif current_max < v:
            current_max = v

        result.append(current_max)

        # 최댓값이 window로부터 빠지면 최댓값을 최저로 설정
        if current_max == window.popleft():
            current_max = float('-inf')

    return result


nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(get_max_sliding_window(nums, k))

 

 

 

[예제2: 부분 문자열이 포함된 최소 윈도우]

문자열 S에서 문자열 T의 모든 요소를 포함한 최소 윈도우에 해당하는 부분 문자열을 구하시오.

 

S = 'ADOBECODEBANC'

T = 'ABC'

 

from collections import Counter


def solution(s, t):
    """
    오른쪽으로 윈도우를 늘려가며 모든 t를 포함하는 포인트 right를 찾고
    왼쪽에서부터 윈도우를 줄여가며 t의 요소중 하나라도 포함하지 않는 포인트 left를 찾아서
    right - left + 1을 리턴해주면 된다.

    :param s: 전체 문자열
    :param t: 찾아야 할 문자들이 포함된 문자열
    :return: 모든 t를 포함하는 s의 부분 리스트 중 최단 리스트의 길이
    """
    # 길이가 t인 윈도우가 인덱스 0 ~ t-1에 걸친 상태 부터 시작한다.
    # 모든 t의 요소가 포함되었는지 확인하기 위해
    #       1. 인덱스를 늘려가면서 어떤 문자가 빠지는지 확인하기 위해 문자별로 카운팅을 해놓고
    #       2. 필요로 하는 모든 문자가 빠졌는지 확인하기 위해 t의 전체 길이(len_t)를 파악한다.
    #       * 카운트가 아직 남은 문자에 한해서만 len_t를 1씩 차감한다. (t = 'aabc'인 경우
    #         윈도우를 늘여가면서 a 두개를 포함한 상태에 다시 a가 나와도 len_t가 줄어들면 안되기
    #         때문이다.
    len_by_ch = Counter(t)
    len_t = len(t)
    # t의 모든 문자를 s가 포함하게 될 때까지 right 포인트를 늘여간다.
    for right in range(len(s)):
        try:
            # t의 문자열에 존재하는 문자라면
            if len_by_ch[s[right]] > 0:
                # 하당하는 t를 구성하는 문자의 카운터를 1 감소 시키고
                len_by_ch[s[right]] -= 1
                # 전체 t의 길이도 1 감소 시킨다.
                len_t -= 1
            if len_t == 0:
                break
        except KeyError:
            pass

    for left in range(0, right - len_t):
        try:
            if len_by_ch[s[left]] == 0:
                break
        except KeyError:
            pass

    return s[left:right + 1]


s = 'ADOBECODEBANC'
t = 'ABC'
print(solution(s, t))