첫 접근
--> set을 이용해서 중복되는 것을 다 지우고, 그 set을 적용한 반환값의 length값을 구하면 된다고 생각했다. 하지만...
그렇게 간단하게 끝날리가 없다.
'contiguous sequence'를 까먹고 있었다.
그래서 어떻게 풀어야할지 몰라 그냥 풀이과정을 보고 이해하기로 했다.
NeetCode Solution
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in charSet: #현재 오른쪽 포인터 r이 가리키는 문자 s[r]이 charSet에 있는지 확인하고 있으면 반복
charSet.remove(s[l]) #왼쪽 포인터 l이 가리키는 문자를 지움
l += 1 #l은 다음 으로 이동
charSet.add(s[r]) #s[r]이 charSet에 없으면 s[r]을 추가
res = max(res, r - l + 1)
#res는 지금까지 나왔던 res의 max값과 오른쪽 포인터에서 왼쪽 포인터를 빼고 1을 더한값(문자열의 길이) 중 최대값을 구함.
#+1을 더하는 이유는 인덱스는 0부터 시작하니까
return resChat GPT말로는 슬라이딩 윈도우 (Sliding Window) 알고리즘이라고 한다.
슬라이딩 윈도우 알고리즘의 동작 원리:
- 윈도우 확장: 오른쪽 포인터 r를 이동하면서 윈도우를 확장합니다. 주어진 조건을 만족하는 동안 오른쪽 포인터를 이동시켜 더 큰 구간을 탐색합니다.
- 윈도우 축소: 조건이 더 이상 만족되지 않으면 왼쪽 포인터 l를 이동시켜 윈도우를 축소합니다.
- 구간 처리: 윈도우가 확장되거나 축소될 때마다 현재 윈도우 내의 구간을 처리하거나 필요한 계산을 수행합니다.
슬라이딩 윈도우 알고리즘이 유용한 문제 유형:
- 최장 중복 없는 부분 문자열 문제 (LeetCode "Longest Substring Without Repeating Characters"): 문자열에서 중복이 없는 가장 긴 부분 문자열의 길이를 구하는 문제입니다
--> 문자열 s가 주어졌을 때, 중복된 문자가 없는 가장 긴 부분 문자열의 길이를 반환합니다.
- 슬라이딩 윈도우로 해결:
- 포인터 설정: 두 포인터 l과 r을 사용해 윈도우의 시작과 끝을 나타냅니다.
- 문자 확인: 오른쪽 포인터 r를 이동시키면서 문자가 중복되었는지 확인합니다. 중복된 문자가 있으면, 왼쪽 포인터 l를 이동시켜 중복을 제거합니다.
- 최대 길이 갱신: 중복 없는 부분 문자열의 길이를 계산하고 그 값을 저장합니다.
def lengthOfLongestSubstring(s: str) -> int:
charSet = set() # 중복 문자를 추적하는 set
l = 0 # 슬라이딩 윈도우의 왼쪽 포인터
max_len = 0 # 결과 값 저장
for r in range(len(s)): # 오른쪽 포인터로 문자열을 순회
# 중복된 문자가 있으면 왼쪽 포인터를 이동하면서 중복 제거
while s[r] in charSet:
charSet.remove(s[l])
l += 1
# 중복 없는 문자를 추가하고 최대 길이 갱신
charSet.add(s[r])
max_len = max(max_len, r - l + 1)
return max_len
- 고정된 크기의 슬라이딩 윈도우 예시 (연속된 구간의 합) : 주어진 배열 arr에서 크기가 k인 연속된 부분 배열의 최대 합을 구하는 문제입니다.
- 슬라이딩 윈도우로 해결:
- 윈도우 설정: 고정된 크기 k를 유지하면서 오른쪽 포인터 r를 이동시켜 윈도우를 확장합니다.
- 윈도우 축소: 오른쪽 포인터가 k를 넘으면 왼쪽 포인터 l를 이동시켜 윈도우를 유지합니다.
def maxSum(arr, k):
window_sum = sum(arr[:k]) # 첫 번째 윈도우의 합
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # 윈도우의 오른쪽으로 이동
max_sum = max(max_sum, window_sum)
return max_sum
- 변동 크기의 슬라이딩 윈도우 문제 (최소 길이 부분 배열) : 주어진 배열에서 합이 S 이상인 부분 배열 중 최소 길이를 구하는 문제입니다.
def minSubArrayLen(S, arr):
l = 0
total = 0
min_len = float('inf')
for r in range(len(arr)):
total += arr[r] # 오른쪽 포인터로 윈도우 확장
while total >= S: # 합이 S 이상이면
min_len = min(min_len, r - l + 1) # 최소 길이 갱신
total -= arr[l] # 왼쪽 포인터 이동하여 윈도우 축소
l += 1
return min_len if min_len != float('inf') else 0
- 최대 K개의 고유 문자를 포함하는 최장 부분 문자열(특정 조건을 만족하는 구간 탐색 문제) : 주어진 문자열에서 최대 K개의 고유 문자를 포함하는 가장 긴 부분 문자열의 길이를 구하세요.
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
if k == 0: # K가 0이면 결과는 0
return 0
char_count = {} # 각 문자의 등장 횟수를 기록할 딕셔너리
l = 0 # 왼쪽 포인터
max_len = 0 # 최장 부분 문자열의 길이
for r in range(len(s)): # 오른쪽 포인터로 문자열 탐색
# 오른쪽 포인터에서 본 문자를 딕셔너리에 추가하거나 개수 증가
char_count[s[r]] = char_count.get(s[r], 0) + 1
# 딕셔너리의 길이가 K를 초과하면
while len(char_count) > k:
char_count[s[l]] -= 1 # 왼쪽 포인터가 가리키는 문자의 개수 감소
if char_count[s[l]] == 0: # 문자의 개수가 0이 되면 딕셔너리에서 제거
del char_count[s[l]]
l += 1 # 왼쪽 포인터 이동하여 윈도우 축소
# 현재 윈도우 크기와 최대 길이를 비교하여 갱신
max_len = max(max_len, r - l + 1)
return max_len
# 테스트
s = "eceba"
k = 2
print(lengthOfLongestSubstringKDistinct(s, k)) # 출력: 3
