알고리즘 기법- 슬라이딩 윈도우

• 1. 슬라이딩 윈도우 기법이란?
  • 1.1 정의
  • 1.2 기본 아이디어
• 2. 슬라이딩 윈도우의 주요 사용 사례
• 3. 슬라이딩 윈도우와 투 포인터
• 4. 연습문제
  • 4.1 고정 길이 부분 배열의 최대 합
  • 4.2 최대 길이의 고유 문자 부분 문자열 찾기

---

1. 슬라이딩 윈도우 기법이란?

1.1 정의

고정된 크기나 가변적인 크기의 ‘윈도우’를 배열이나 문자열 위에서 이동시키면서 특정 조건을 만족하는 값을 찾는 방법.

1.2 기본 아이디어

• 윈도우의 크기를 설정하고 초기 위치에서 시작.
• 윈도우를 오른쪽으로 한 칸씩 이동시키면서 윈도우 내의 값을 업데이트.
• 각 윈도우 상태에서 필요한 값을 계산하고, 조건을 만족하는 최적의 값을 찾기.

2. 슬라이딩 윈도우의 주요 사용 사례

• 최대/최소 부분 배열 합 찾기
• 부분 배열 평균 계산
• 문자열에서 특정 패턴 찾기

3. 슬라이딩 윈도우와 투 포인터

투 포인터가 슬라이딩 윈도우의 일종에 가깝다. 둘 다 배열이나 문자열과 같은 선형 자료 구조에서 특정 조건을 만족하는 부분 배열이나 부분 문자열을 찾는 데 사용된다.

• 슬라이딩 윈도우를 사용한다고 해서 꼭 투 포인터를 사용하는 건 아니다. 고정 크기의 윈도우를 사용하는 경우는 투 포인터가 필요 없다. 하지만 가변적인 크기의 윈도우를 사용하는 경우에는 보통 투 포인터를 사용한다.
• 투 포인터를 사용한다는 것은, 슬라이딩 윈도우의 개념을 기반으로 한다.

기법	슬라이딩 윈도우	투 포인터
효율성	연속된 부분 배열의 합이나 평균을 계산할 때 효율적	특정 조건을 만족하는 부분 배열을 찾을 때 효율적
사용 사례	최대/최소 부분 배열 합, 평균 계산 등	특정 합을 갖는 부분 배열, 특정 조건 만족 구간 찾기

4. 연습문제

4.1 고정 길이 부분 배열의 최대 합

'''
문제 설명
주어진 배열에서 길이가 k인 모든 연속된 부분 배열의 합 중에서 최대 값을 구하시오.

입력
첫 번째 줄에 배열의 길이 n과 부분 배열의 길이 k가 주어집니다. (1 ≤ k ≤ n ≤ 100,000)
두 번째 줄에 배열의 원소 n개가 공백으로 구분되어 주어집니다. 배열의 원소는 정수입니다.

출력
길이가 k인 모든 연속된 부분 배열의 합 중에서 최대 값을 출력합니다.

예제 입력
8 3
1 2 3 4 5 6 7 8

예제 출력
18

설명
길이가 3인 부분 배열의 합은 다음과 같습니다:
[1, 2, 3]의 합: 6
[2, 3, 4]의 합: 9
[3, 4, 5]의 합: 12
[4, 5, 6]의 합: 15
[5, 6, 7]의 합: 18
[6, 7, 8]의 합: 21
따라서 최대 값은 21입니다.
'''

import sys

input = sys.stdin.readline

length_of_arr, length_of_part = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

left: int = 0
window_sum = sum(arr[:length_of_part])
max_sum: int = window_sum

for index in range(length_of_part, length_of_arr):
    window_sum += arr[index] - arr[index - length_of_part]
    max_sum = max(max_sum, window_sum)

print(max_sum)

4.2 최대 길이의 고유 문자 부분 문자열 찾기

'''

문제 설명
주어진 문자열에서 모든 문자가 고유한 가장 긴 부분 문자열의 길이를 구하세요.

입력
문자열 s가 주어집니다. 문자열의 길이는 1 이상 100,000 이하입니다.

출력
모든 문자가 고유한 가장 긴 부분 문자열의 길이를 출력합니다.

예제 입력
abcabcbb

예제 출력
3

설명
입력 문자열 abcabcbb에서 모든 문자가 고유한 가장 긴 부분 문자열은 abc로, 길이는 3입니다.
'''

import sys

input = sys.stdin.readline

source_str = input().rstrip()

left: int = 0
max_length_of_unique_char: int = 0
char_set = set() # 현재 윈도우 내의 고유 문자를 저장하는 집합

for right in range(len(source_str)):
    # 현재 문자가 이미 집합에 있는 경우, 중복 문자가 없어질 때까지 왼쪽 포인터를 이동
    while source_str[right] in char_set:
        char_set.remove(source_str[left])
        left += 1
    char_set.add(source_str[right])
    max_length_of_unique_char = max(max_length_of_unique_char, right - left + 1)

print(max_length_of_unique_char)