📌 75) 최대 슬라이딩 윈도우 ( 리트코드 239. Sliding Window Maximum )
✔ 풀이1 (브루트 포스로 계산) Time Limit Exceeded
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
max_values = []
for i in range(len(nums) - k + 1):
max_values.append(max(nums[i: i+k]))
return max_values✔ 풀이2 (큐를 이용한 최적화) Time Limit Exceeded
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
cur_max = float('-inf')
answer = []
for i, n in enumerate(nums):
q.append(n)
if i < k - 1:
continue
if cur_max == float('-inf'): #최대값이 초기화 됫을 경우
cur_max = max(q) #최대값 다시 계산
elif n > cur_max: #추가 한 값이 최대값일 경우
cur_max = n #최대값 변경
answer.append(cur_max)
if q.popleft() == cur_max: #최대값이 빠져나갔을 경우
cur_max = float('-inf') #최대값 초기화
return answer풀이1과는 다르게 필요할 때만 전체의 최대값을 계산하고 이외에는 새로 추가되는 값이 최대인지만을 확인하는 형태로 계산량을 줄임
👉 그래도 시간 초과 발생함 (n이 매우 큰 경우 시간 초과 발생)
👉 조금 더 최적화 필요
✔ 풀이3 (max사용하지 X)
from collections import deque
class Solution:
#0에 최대값의 인덱스 위치하도록 만들어 주는 메소드
def add_to_dq(self, nums, dq, idx):
#새로 추가할 값 보다 이하면 pop()
#=> dq의 마지막 값이 새로 추가할 값 보다 큰 값을 가질때까지 pop
while dq and nums[dq[-1]] <= nums[idx]:
dq.pop()
dq.append(idx)
return
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque()
#초기 윈도우 설정
for i in range(k):
self.add_to_dq(nums, dq, i)
answer = []
start, end = 0, k - 1 #초기 윈도우의 시작과 끝
while end < len(nums):
while 1:
if dq and dq[0] >= start: #최대값이 윈도우 범위 안에 존재 할 경우
answer.append(nums[dq[0]])
break
else:
dq.popleft()
start, end = start + 1, end + 1 #다음 윈도우
if end < len(nums):
self.add_to_dq(nums, dq, end)
return answer👉최대값을 계산하는 max 메소드 사용하지 않고 deque자료구조를 사용하여 최대값의 인덱스가 deque[0]에 존재하도록 구성
👉최대값이 아닌 최대값의 인덱스를 deque에 추가하는 이유?
deque[0]에 존재하는 최대값의 인덱스가 슬라이딩 윈도우의 범위내에 존재하는지 판별하기 위해!
✔ 풀이4 (풀이3 코드 정리)
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
answer = []
dq, start = deque(), 0
for i, n in enumerate(nums):
#dq[0]은 최대값의 인덱스
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
if i < k - 1: #dq초기값 생성하기 위해 0,1,..,k-2은 위에만 반복
continue
while 1:
if dq[0] >= start: #최대값이 범위 안에 존재할 경우
answer.append(nums[dq[0]])
break
else:
dq.popleft()
start += 1 #시작위치 + 1
return answer📌 76) 부분 문자열이 포함된 최소 윈도우 ( 리트코드 76. Minimum Window Substring )
✔ 풀이1 (모든 윈도우 크기를 브루트 포스로 탐색) Time Limit Exceeded
class Solution:
def minWindow(self, s: str, t: str) -> str:
def contains(sub_list, t_list): #sub_s가 t_s를 포함하는지 여부 return
for t in t_list:
if t in sub_list:
sub_list.remove(t)
else:
return False
return True
min_size = len(t)
for size in range(min_size, len(s) + 1):
for start in range(len(s) - size + 1):
sub = s[start: start + size]
if contains(list(sub), list(t)):
return sub
return ""✔ 풀이2 (투 포인터, 슬라이딩 윈도우로 최적화)
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
missing = len(t) #찾아야 할 문자 개수
left, start, end = 0, 0, 0
for right, char in enumerate(s):
missing -= need[char] > 0
need[char] -= 1 #char가 존재하지 않으면 0-1 = -1 (음수)
if missing == 0: #모든 문자 다 찾았을 경우
#left가 필요한 문자를 가르키도록 이동
while left < right and need[s[left]] < 0:
need[s[left]] += 1
left += 1
#더 작은 범위를 start, end에 저장
if not end or right - left < end - start:
start, end = left, right
need[s[left]] += 1
missing += 1
left += 1
if start == 0 and end == 0 and (t != s[0]): #예외처리
return ""
return s[start: end + 1]📌 77) 가장 긴 반복 문자 대체 ( 리트코드 424. Longest Repeating Character Replacement )
✔ 풀이 (투 포인터, 슬라이딩 윈도우, Counter를 모두 이용)
from collections import Counter
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = Counter()
left = 0
for right in range(1, len(s) + 1):
counts[s[right - 1]] += 1
max_char_n = counts.most_common(1)[0][1] #윈도우 내의 가장 많이 있는 문자 개수
#윈도우 내의 전체 문자 개수(right-left) - 윈도우 내의 가장 많이 있는 문자 개수
#= 변경해야 할 문자 개수
if right - left - max_char_n > k:
counts[s[left]] -= 1
left += 1
return right - left