최대 슬라이딩 윈도우

Question 75: 최대 슬라이딩 윈도우

배열 nums가 주여졌을 때 k 크기의 슬라이딩 윈도우를 오르쪽 끝까지 이동하면서 최대 슬라이딩 윈도우를 구하여라.

입력: nums = [1,3,-1,-3,5,3,6,7], k = 3

출력: [3,3,5,5,6,7]

---

내 풀이

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        
        result = []
    
        for i in range(len(nums)-k+1):
            result.append(max(nums[i:i+k]))
        
        return result

결과

시간 초과 에러가 떴다.

풀이 1: 브루트 포스로 계산

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return None
        result = []
    
        for i in range(len(nums)-k+1):
            result.append(max(nums[i:i+k]))
        
        return result

중요 내용

1. 앞에 nums가 입력값이 없을때 예외 처리하는 것을 제외하고 내 풀이 방법과 동일하게 풀이하였다.
2. 책에서는 풀이가 704ms 만큼 소모되었다고 나왔는데 실제로 계산해보니 시간 초과 에러가 떴다.

풀이 2: 큐를 이용한 최적화

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results = []
        window = collections.deque()
        current_max = float('-inf')
        for i, v in enumerate(nums):
            window.append(v)
            if i < k - 1:
                continue

            # 새로 추가된 값이 기존 최대값보다 큰 경우 교체
            if current_max == float('-inf'):
                current_max = max(window)
            elif v > current_max:
                current_max = v

            results.append(current_max)

            # 최대값이 윈도우에서 빠지면 초기화
            if current_max == window.popleft():
                current_max = float('-inf')
                
        return results
        

중요 내용

1. 윈도우 변수를 만들고 윈도우의 최댓값과 윈도우를 이동하면서 새로 추가되는 값간의 크기를 비교한다.
2. 풀이1과 마찬가지로 책에서는 풀이가 156ms 만큼 소모되었다고 나왔는데 실제로 계산해보니 시간 초과 에러가 떴다.

---

Question 76: 부분 문자열이 포함된 최소 윈도우(재풀이)

문자열 S와 T를 입력받아 O(n) 에 T에 모든 문자가 포함된 S의 최소 윈도우를 찾아라.

입력: s = “ADOBECODEBANC”, t = “ABC”

출력: “BANC”

---

내 풀이

브루트 포스 방법으로 접근하려 했으나 시간 복잡도가 O(n) 으로 제한되어 있어 결국 풀지 못하였다.

풀이 1: 브루트 포스로 풀이

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        def contains(s_substr_lst: List, t_lst: List):
            for t in t_lst:
                if t in s_substr_lst:
                    s_substr_lst.remove(t)
                else:
                    return False
            return True
        
        init_window_size = len(t)
        
        for window_size in range(init_window_size, len(s)+1):
            for i in range(len(s)-window_size+1):
                if contains(list(s[i:i+window_size]), list(t)):
                    return s[i:i+window_size]
        
        return ''
            

중요 내용

1. T의 크기부터 시작해 점점 크기를 키워가며 모든 윈도우 크기에 대해 탐색을 시도해 보는 풀이 방법이다.
2. 시간 복잡도가 $O(n^2)$ 이므로 시간 초과 에러가 떴다.

풀이 2: 투 포인터, 슬라이딩 윈도우로 최적화

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        missing = len(t)
        left = start = end = 0
        
        # 오른쪽 포인터 이동
        for right, char in enumerate(s,1):
        
            # char이 need에 키로 들어가 있고 need에 해당하는 value 값이 0보다 크면 missing 에서 1을 뺀다.
            missing -= need[char] > 0 
            need[char] -= 1
        
            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]
            

중요 내용

1. 우측으로 이동하며 크기가 증가하는 슬라이딩 윈도우에서 윈도우 안에 T에 들어있는 값이 모두 들어있는 경우 왼쪽 포인터를 줄이면서 가장 최소인 윈도우를 찾는다.
2. 왼쪽 포인터를 이동할지 여부는 딕셔너리에서 해당 문자의 value가 음수일때이다. value가 0이 되는 key 값에 도달할 때까지 왼쪽 포인터를 이동한다.
3. counter() 함수를 사용하면 defaultdict와 비슷하게 설정하지 않은 key 값에 대한 value는 0이다.

풀이 3: counter로 좀 더 편리한 풀이

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 ''
            

중요 내용

1. current_count는 오른쪽 포인터가 이동하면서 만든 딕셔너리이고 t_count는 t의 요소의 개수를 나타낸 딕셔너리이다. 이 두개의 변수의 AND 연산 결과를 t_count와 비교하여 같으면 왼쪽 포인터를 이동하고, 다르면 이동하지 않는다.
2. 그러나 이 풀이방법은 AND 연산이 무겁기 때문에 시간 초과 에러가 뜬다.

---

Question 77: 가장 긴 반복 문자 대체

대문자로 구성된 문자열 s가 주어졌을 때 k번 만큼의 변경으로 만들 수 있는 연속으로 반복된 문자열의 가장 긴 문자열을 구하여라.

입력: s = “AABABBA”, k = 1

출력: 4

---

풀이 1: 투 포인터, 슬라이딩 윈도우 이용

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        counts = collections.Counter()
        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            max_char_n = counts.most_common(1)[0][1]
            
            # k 초과시 왼쪽 포인터 이동
            if right - left - max_char_n > k:
                counts[s[left]] -= 1
                left += 1
                
        return right - left

중요 내용

1. max(right) - max(left) - max_char_n == k 을 만족하는 right 와 left 의 차이를 구하는 것이 이 풀이 방법의 목적이다.
2. 오른쪽 포인터는 계속 커지기 때문에 최댓값을 추출하기 위해서는 왼쪽 포인터는 이동하지 않는 것이 좋으나 만약 k 연산 횟수를 넘어서면 왼쪽 포인터를 더 크게한다.

---