슬라이딩 윈도우

제로베이스 7월 기업 코테 라이브 특강 / 김태원

슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)은 배열이나 문자열과 같은 데이터 구조에서 연속된 부분 데이터를 효율적으로 처리하기 위한 기법입니다. 이 알고리즘은 주로 일정 크기의 윈도우를 데이터의 시작부터 끝까지 순차적으로 이동시키면서 필요한 연산을 수행합니다. 슬라이딩 윈도우 알고리즘은 종종 최적화 문제에서 사용되며, 시간 복잡도를 줄이는 데 큰 도움이 됩니다.

슬라이딩 윈도우 알고리즘의 주요 아이디어

1. 윈도우 정의: 고정된 크기의 윈도우를 정의합니다. 이 윈도우는 배열이나 문자열의 일부분을 나타냅니다.
2. 윈도우 초기화: 윈도우를 데이터 구조의 시작 부분에 배치하고, 초기 값을 계산합니다.
3. 윈도우 이동: 윈도우를 한 요소씩 오른쪽으로 이동시키면서, 윈도우의 시작점과 끝점을 조정합니다.
4. 이 과정에서 윈도우 내의 데이터를 업데이트하고 필요한 연산을 수행합니다.

예제: 최대 부분 배열 합 (Maximum Sum of Subarray)

문제

주어진 배열에서 k 길이의 연속된 부분 배열의 합이 최대가 되는 값을 찾으시오.

접근법

1. 브루트 포스 접근법
   • 모든 가능한 부분 배열을 계산하여 최대 합을 찾습니다. 시간 복잡도는 O(n^2)입니다.
2. 슬라이딩 윈도우 접근법
   • 윈도우를 사용하여 배열의 요소를 한 번만 순회하면서 최대 합을 계산합니다. 시간 복잡도는 O(n)입니다.

코드 구현 (Java)

class Main {
    public int solution(int[] nums, int k){
        int answer, sum = 0;
        for(int i = 0; i < k; i++) sum += nums[i];
        answer = sum;
        for(int i = k; i < nums.length; i++){
            sum += (nums[i] - nums[i - k]);
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        int[] arr = new int[]{3, 5, 6, 8, 9, 7, 2, 1};
        System.out.println(T.solution(arr, 3));
    }
}

import java.util.*;
class Main {
	public int solution(int[] nums, int k){
		int answer, sum=0;
		for(int i = 0; i < k; i++) sum += nums[i];
		answer = sum;
		int left = 0;
		for(int right = k; right < nums.length; right++){
			sum += (nums[right]-nums[left]);
			answer = Math.max(answer, sum);
			left++;
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		int[] arr = new int[]{3, 5, 6, 8, 9, 7, 2, 1};
		System.out.println(T.solution(arr, 3));	
	}
}

설명

1. 윈도우 초기화: 처음 k개의 요소 합을 계산합니다.
2. 윈도우 이동: 배열의 나머지 요소를 순회하며 윈도우를 오른쪽으로 한 칸씩 이동시키면서 최대 합을 갱신합니다.
3. 최종 결과: 최대 합을 반환합니다.

이 알고리즘은 윈도우를 사용하여 배열을 한 번만 순회하기 때문에 시간 복잡도는 O(n)으로 효율적입니다.

연습문제

최대 매출

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 합 중에서 최대값이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

12 15 11 20 25 10 20 19 13 15

연속된 3일간의 최대 매출액은 11 + 20 + 25 = 56만원입니다.

여러분이 현수를 도와주세요.

입력 설명

• 첫 번째 줄에 자연수 N(5 <= N <= 100,000)이 주어집니다.
• 두 번째 줄에 N일 동안의 매출액이 주어집니다. 각 매출액은 500 이하의 자연수입니다.
• 세 번째 줄에 K(2 <= K <= N)가 주어집니다.

출력 설명

• 첫 번째 줄에 최대 매출액을 출력합니다.

입력 예제 1

10
12 15 11 20 25 10 20 19 13 15
3

출력 예제 1

56

입력 예제 2

9
1 2 3 5 6 7 1 3 9
5

출력 예제 2

26

입력 예제 3

10
12 34 56 72 93 121 33 11 23 52
4

출력 예제 3

342

import java.util.*;
class Main {
	public int solution(int[] nums, int k){
		int answer, sum=0;
		for(int i = 0; i < k; i++) sum += nums[i];
		answer = sum;
		int left = 0;
		for(int right = k; right < nums.length; right++){
			sum += (nums[right]-nums[left]);
			left++;
                        answer = Math.max(answer, sum);
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++){
			arr[i] = kb.nextInt();
		}
		int k = kb.nextInt();
		System.out.println(T.solution(arr, k));	
	}
}

연속 부분수열 1

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정 숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N = 8, M = 6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

입력 설명

• 첫 번째 줄에 자연수 N(3 <= N <= 100,000)이 주어집니다.
• 두 번째 줄에 N길이의 수열이 주어집니다. 수열의 원소 값은 1000을 넘지 않는 자연수입니다.
• 세 번째 줄에 M(1 ≤ M ≤ 100,000,000)이 주어집니다.

출력 설명

• 첫 번째 줄에 모든 경우의 수를 출력합니다.

입력 예제 1

8
1 2 1 3 1 1 1 2
6

출력 예제 1

3

입력 예제 2

6
1 1 1 1 1 1
3

출력 예제 2

4

입력 예제 3

7
1 2 1 2 1 2 1
3

출력 예제 3

6

import java.util.*;
class Main {
	public int solution(int[] nums, int m){
		int answer = 0, sum=0;
		int left = 0;
		for(int right = 0; right < nums.length; right++){
			sum += nums[right];
			while(sum > m){
				sum -= nums[left];
				left++;
			}
			if(sum == m) answer++;
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++){
			arr[i] = kb.nextInt();
		}
		int m = kb.nextInt();
		System.out.println(T.solution(arr, m));	
	}
}

연속 부분수열 2

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정 숫자 M 이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N = 5, M = 5이고 수열이 다음과 같다면

1 3 1 2 3

합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다.

입력 설명

• 첫 번째 줄에 자연수 N(3 <= N <= 100,000)이 주어집니다.
• 두 번째 줄에 N길이의 수열이 주어집니다. 수열의 원소 값은 1000을 넘지 않는 자연수입니다.
• 세 번째 줄에 M(1 ≤ M ≤ 100,000,000)이 주어집니다.

출력 설명

• 첫 번째 줄에 모든 경우의 수를 출력합니다.

입력 예제 1

5
1 3 1 2 3
5

출력 예제 1

10

입력 예제 2

6
1 1 1 1 1 1
3

출력 예제 2

15

입력 예제 3

9
1 1 2 2 1 2 1 3 2
5

출력 예제 3

22

import java.util.*;
class Main {
	public int solution(int[] nums, int m){
		int answer = 0, sum=0;
		int left = 0;
		for(int right = 0; right < nums.length; right++){
			sum += nums[right];
			while(sum > m){
				sum -= nums[left];
				left++;
			}
			answer += (right - left + 1);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++){
			arr[i] = kb.nextInt();
		}
		int m = kb.nextInt();
		System.out.println(T.solution(arr, m));	
	}
}

투 포인터스 알고리즘의 핵심 아이디어:

right 포인터를 하나씩 증가시키면서 현재 부분수열의 합을 sum에 더합니다. sum이 m을 초과하면, sum이 m 이하가 될 때까지 left 포인터를 오른쪽으로 이동시키며 부분수열의 시작을 조정합니다. answer에 (right - left + 1)을 더하는 이유는, 현재 right 위치에서 끝나는 부분수열의 개수를 계산하기 위해서입니다. 이 수는 left부터 right까지 모든 가능한 부분수열의 개수를 나타냅니다.

예제 N = 5, M = 5, nums = [1, 3, 1, 2, 3]인 경우를 생각해봅시다.

초기 상태 sum = 0 answer = 0 left = 0 right 포인터를 이동하면서 계산 right = 0

sum = sum + nums[0] = 0 + 1 = 1 sum (1) <= M (5), answer += (right - left + 1) = 1 현재 부분수열: [1] answer = 1 right = 1

sum = sum + nums[1] = 1 + 3 = 4 sum (4) <= M (5), answer += (right - left + 1) = 2 현재 부분수열: [1, 3], [3] answer = 3 right = 2

sum = sum + nums[2] = 4 + 1 = 5 sum (5) <= M (5), answer += (right - left + 1) = 3 현재 부분수열: [1, 3, 1], [3, 1], [1] answer = 6 right = 3

sum = sum + nums[3] = 5 + 2 = 7 sum (7) > M (5), while 루프 진입: sum = sum - nums[left] = 7 - 1 = 6, left = 1 sum (6) > M (5), while 루프 계속: sum = sum - nums[left] = 6 - 3 = 3, left = 2 sum (3) <= M (5), answer += (right - left + 1) = 2 현재 부분수열: [1, 2], [2] answer = 8 right = 4

sum = sum + nums[4] = 3 + 3 = 6 sum (6) > M (5), while 루프 진입: sum = sum - nums[left] = 6 - 1 = 5, left = 3 sum (5) <= M (5), answer += (right - left + 1) = 2 현재 부분수열: [2, 3], [3]

최종 결과 answer = 10

연속된 자연수의 합

입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.

만약 N = 15이면

7 + 8 = 15
4 + 5 + 6 = 15
1 + 2 + 3 + 4 + 5 = 15

와 같이 총 3가지의 경우가 존재합니다.

입력 설명

• 첫 번째 줄에 양의 정수 N(7 <= N < 100,000)이 주어집니다.

출력 설명

• 첫 번째 줄에 총 경우수를 출력합니다.

입력 예제 1

15

출력 예제 1

3

입력 예제 2

45678

출력 예제 2

7

입력 예제 3

98765

출력 예제 3

3

import java.util.*;
class Main {	
	public int solution(int n){
		int answer = 0;
		int sum = 0;
		int left = 1;
		for(int right = 1; right <= n/2+1; right++){
			sum += right;
			while(sum > n){
				sum -= left;
				left++;
			}
			if(sum == n) answer++;
		}

		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();	
		System.out.println(T.solution(n));
	}
}

import java.util.*;
class Main {	
	public int solution(int n){
		int answer = 0;
		n--;
		int cnt = 1;
		while(n > 0){
			cnt++;
			n = n - cnt;
			if(n % cnt == 0) answer++;
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();	
		System.out.println(T.solution(n));
	}
}

사과

현수는 사과나무 밑에 있습니다. 현수는 한 번의 점프로 사과나무에서 여러 개의 사과를 딸 수 있습니다. 현수는 매초 점프를 합니다. 그리고 우리는 현수가 매초 점프할 때의 얻을 수 있는 사과의 개수를 미리 알고 있습니다. 그런데 현수는 어떤 초에는 에너지가 없어 점프를 할 수 없습니다. 하지만 우리에게는 현수가 에너지가 없어도 M초 동안은 무조건 점프를 해서 사과를 딸 수 있게 하는 부스트 기술이 있습니다.

현수가 1초부터 N초까지 매초 차례대로 딸 수 있는 사과의 개수 정보가 주어지고, 1초부터 N초까지 매초 에너지의 상태가 주어지면 부스트 기술까지 사용해서 딸 수 있는 사과의 최대 총 개수를 출력하는 프로그램을 작성하세요.

입력 설명

• 첫 번째 줄에 자연수 N(1 <= N <= 500,000)이 주어집니다.
• 두 번째 줄에 N초 동안 딸 수 있는 사과의 개수 정보가 주어집니다. 1초에 딸 수 있는 사과의 개수는 9 이하입니다.
• 세 번째 줄에 N초 동안의 에너지 상태가 주어집니다. 1은 점프를 할 수 있는 상태이고, 0은 점프를 할 수 없는 상태입니다.
• 마지막 줄에 M(2 <= M <= N의 길이)이 주어집니다.

출력 설명

• 첫 번째 줄에 현수가 딸 수 있는 사과의 최대 개수를 출력합니다.

입력 예제 1

6
3 2 1 2 1 3
1 0 0 1 0 0
3

출력 예제 1

9

입력 예제 2

9
3 2 3 2 1 3 3 6 7
1 0 0 1 0 0 0 0 0
5

출력 예제 2

25

문제 풀이

이 문제는 슬라이딩 윈도우 기법을 사용하여 해결할 수 있습니다. 주어진 초 동안 에너지가 있는 상태에서는 사과를 딸 수 있고, 없는 상태에서는 부스트를 사용하여 사과를 딸 수 있습니다. 부스트는 최대 M초 동안 사용할 수 있습니다.

1. 사과 개수 계산:
   • 에너지가 있는 상태에서 딸 수 있는 사과 개수를 먼저 계산합니다.
2. 부스트를 사용한 최대 사과 개수 계산:
   • 슬라이딩 윈도우를 사용하여 부스트를 사용할 수 있는 최대 M초 동안 딸 수 있는 사과 개수를 계산합니다.

import java.util.*;
class Main {
	public int solution(int n, int[] apple, int[] energy, int m){
		int answer = 0, sum = 0;
		for(int i = 0; i < n; i++){
			if(energy[i] == 1) sum += apple[i];
		}
		for(int i = 0; i < m; i++){
			if(energy[i] == 0) sum += apple[i];
		}
		answer = sum;
		int left = 0;
		for(int right = m; right < n; right++){
			if(energy[right] == 0) sum += apple[right];
			if(energy[left] == 0) sum -= apple[left];
			left++;
			answer = Math.max(answer, sum);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] a = new int[n];
		int[] e = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = kb.nextInt();
		}
		for(int i = 0; i < n; i++){
			e[i] = kb.nextInt();
		}
		int m = kb.nextInt();
		System.out.println(T.solution(n, a, e, m));	
	}
}

최대 길이 연속부분수열

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.

만약 길이가 14인 다음과 같은 수열이 주어지고 k = 2라면

1 1 0 0 1 1 0 1 1 0 1 1 0 1

만들 수 있는 1이 연속된 최대 길이의 연속부분수열은 1 1 0 0 1 1 1 1 1 1 1 1 0 1이며 그 길이는 8입니다.

입력 설명

• 첫 번째 줄에 N(5 <= N < 100,000)이 주어지고, 그 다음 줄에 N개의 수열원소가 주어집니다.
• 세 번째 줄에 k가 주어집니다.

출력 설명

• 첫 번째 줄에 최대 길이를 반환하세요.

입력 예제 1

14
1 1 0 0 1 1 0 1 1 0 1 1 0 1
2

출력 예제 1

8

입력 예제 2

18
1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0
4

출력 예제 2

9

import java.util.*;
class Main {
	public int solution(int n, int[] nums, int k){
		int answer = 0, cnt = 0;
		int left = 0;
		for(int right = 0; right < n; right++){
			if(nums[right] == 0) cnt++;
			while(cnt > k){
				if(nums[left] == 0) cnt--;
				left++;
			}
			answer = Math.max(answer, right-left+1);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = kb.nextInt();
		}
		int k = kb.nextInt();
		System.out.println(T.solution(n, a, k));	
	}
}

카드 가져가기

N개의 카드가 일렬로 놓여져 있습니다. 각 카드에는 숫자가 적혀있습니다. 현수는 카드가 일렬로 놓여있는 줄의 양 끝에서 카드를 가져갈 수 있습니다. 현수는 양 끝에서 가져가는 방식으로 K개의 카드를 가져갈 수 있습니다. 그리고 가져간 카드에 적혀진 숫자의 총합이 현수가 얻는 점수입니다. 일렬로 놓여있는 카드의 숫자가 주어지고, 현수가 가져갈 수 있는 카드의 개수 K가 주어지면 현수가 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하세요.

입력 설명

• 첫 번째 줄에 N(5 <= N < 300,000)이 주어집니다.
• 두 번째 줄에 N개의 카드에 적힌 숫자가 일렬로 놓여있는 순서대로 주어집니다. 각 카드의 숫자는 100을 넘지 않는 자연수입니다.
• 세 번째 줄에 K가 주어집니다.

출력 설명

• 첫 번째 줄에 최대 점수를 출력합니다.

입력 예제 1

7
2 3 7 1 2 1 5
4

출력 예제 1

17

입력 예제 2

5
1 30 5 6 7
3

출력 예제 2

38

입력 예제 3

9
1 2 3 5 6 7 1 3 9
5

출력 예제 3

26

문제 풀이

이 문제는 슬라이딩 윈도우 기법을 사용하여 효율적으로 해결할 수 있습니다. 양 끝에서 카드를 선택할 수 있으므로, 왼쪽에서 i개, 오른쪽에서 K-i개의 카드를 선택하는 모든 경우를 고려합니다.

1. 왼쪽과 오른쪽의 점수 계산:
   • 왼쪽에서 0개부터 K개까지 선택한 카드의 점수를 미리 계산합니다.
   • 오른쪽에서 0개부터 K개까지 선택한 카드의 점수를 미리 계산합니다.
2. 최대 점수 계산:
   • 왼쪽에서 i개, 오른쪽에서 K-i개의 카드를 선택했을 때의 점수를 합산하여 최대 점수를 갱신합니다.

import java.util.*;
class Main {
	public int solution(int n, int[] nums, int k){
		int answer = 0, sum = 0;
		for(int i = 0; i < n; i++){
			answer += nums[i];
		}
		int m = n - k;
		for(int i = 0; i < m; i++) sum += nums[i];
		int minS = sum; 
		int left = 0;
		for(int right = m; right < n; right++){
			sum += nums[right];
			sum -= nums[left++];
			minS = Math.min(minS, sum);
		}
		return answer - minS;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = kb.nextInt();
		}
		int k = kb.nextInt();
		System.out.println(T.solution(n, a, k));	
	}
}

문제 팁: 그리디 방법으로 풀면 예외 케이스때문에 틀림. 슬라이딩 윈도우로 n개에서 k개 뽑으면 n-k개가 남는데 이걸 m으로 두고 m구간 합들의 최소값을 구하는 문제임.

공사비용

현수의 마을 앞은 N개의 구간으로 구분되어 있는 2차선 도로가 있습니다. 그런데 이 도로가 이번 비 피해로 파손되어 보수 공사를 해야 합니다. 각 구간별로 보수 공사비용이 다릅니다. 주어진 예산(M원) 안에서 보수 공사를 해 가장 긴 연속 구간을 정상으로 만들고 싶습니다.

아래 표는 8개의 구간으로 나누어진 도로의 각 구간별 공사비용입니다.

구간	0	1	2	3	4	5	6	7
공사비용	0	150	100	10	150	10	70	140

만약 여러분에게 주어진 예산이 350원이라면 공사를 해 정상 구간으로 만들 수 있는 가장 긴 연속 구간은 2구간부터 6구간까지로 비용이 100+10+150+10+70=340원입니다. 연속된 정상 구간의 길이는 구간의 개수를 의미하며 2구간부터 6구간까지는 그 길이가 5입니다.

각 구간의 공사비용 정보가 주어지고, 예산이 주어지면, 주어진 예산 안에서 정상으로 만들 수 있는 가장 긴 연속 구간의 길이를 구하는 프로그램을 작성하세요.

입력 설명

• 첫 번째 줄에 N(5 <= N < 300,000)이 주어집니다.
• 두 번째 줄에 N개의 구간의 보수 공사비용이 주어집니다. 각 구간의 비용은 500을 넘지 않는 자연수입니다.
• 세 번째 줄에 예산인 M이 주어집니다. M은 1,000,000,000 넘지 않습니다.

출력 설명

• 첫 번째 줄에 주어진 예산으로 만들 수 있는 정상인 최대 연속 구간을 출력합니다.

입력 예제 1

8
0 150 100 0 150 0 70 140
350

출력 예제 1

5

입력 예제 2

8
100 50 120 50 150 0 30 60
400

출력 예제 2

6

import java.util.*;
class Main {
	public int solution(int n, int[] cost, int m){
		int answer = 0, sum = 0;
		int left = 0;
		for(int right = 0; right < n; right++){
			sum += cost[right];
			while(sum > m){
				sum -= cost[left];
				left++;
			}
			answer = Math.max(answer, right-left+1);
		}	
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = kb.nextInt();
		}
		int k = kb.nextInt();
		System.out.println(T.solution(n, a, k));	
	}
}

유니크한 부분문자열

문자열이 주어지면 문자가 k종류이면서 최소길이를 갖는 부분문자열을 구하고 싶습니다. 만약 입력된 문자열이 “abacbbcdede” 이고 k=5이면 “acbbcde” 부분문자열이 문자종류가 5인 최소길이 부분문자열입니다. 매개변수 s에 문자열이 주어지고, k가 주어지면 k종류의 문자를 갖는 최소길이 부분문자열을 반환하는 프로그램을 작성하세요.

제한사항

• s의 길이는 300,000을 넘지 않습니다.
• s는 소문자로만 구성되어 있습니다.
• 2 <= k < s의 길이

입력과 출력 예

s	k	answer
“abacbbcdede”	5	7
“acbbcdbbedeade”	4	5
“abcabcabcbebef”	5	8
“aaccabcabbbbcbebef”	5	11
“afgaccfabcabbgfhbbcbetyebef”	7	9

import java.util.*;
class Solution {
	public int solution(String s, int k){
		int answer = 300000;
		HashMap<Character, Integer> sH = new HashMap<>();
		int left = 0;
		for(int right = 0; right < s.length(); right++){
			sH.put(s.charAt(right), sH.getOrDefault(s.charAt(right), 0) + 1);
			while(sH.size() == k){
				answer = Math.min(answer, right-left+1);
				sH.put(s.charAt(left), sH.get(s.charAt(left)) - 1);
				if(sH.get(s.charAt(left)) == 0) sH.remove(s.charAt(left));
				left++;
			}
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution("abacbbcdede" , 5));
		System.out.println(T.solution("acbbcdbbedeade", 4));
		System.out.println(T.solution("abcabcabcbebef", 5));
		System.out.println(T.solution("aaccabcabbbbcbebef", 5));
		System.out.println(T.solution("afgaccfabcabbgfhbbcbetyebef", 7));
	}
}

음수가 있는 부분수열

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 알고싶습니다.

예를 들어, 주어진 수열이 [1, 2, 3, -3, 1, 2, 2, -3]이고, M값이 5이라면 합이 5가 되는 연속부분수열은 [2, 3], [2, 3, -3, 1, 2], [1, 2, 2], [3, -3, 1, 2, 2], [1, 2, 3, -3, 1, 2, 2, -3]로 총 5가지입니다.

매개변수 nums에 길이가 N인 수열이 주어지고, 매개변수 m에 M값이 주어지면 연속부분수열의 합이 M인 연속부분수열의 경우수를 반환하는 프로그램을 작성하세요.

제한사항

• nums의 길이는 200,000을 넘지 않는다.
• M(-100,000,000 ≤ M ≤ 100,000,000)
• 수열의 원소값은 -1000부터 1,000까지의 정수입니다.

입력과 출력 예

nums	m	answer
[2, 2, 3, -1, -1, -1, 3, 2, 1]	5	6
[1, 2, 3, -3, 1, 2, 2, -3]	5	5
[1, 2, 3, -3, 1, 2]	3	6
[-1, 0, 1]	0	2
[-1, -1, -1, 1]	0	1

import java.util.*;
class Solution {
	public int solution(int[] nums, int m){
		int answer = 0;
		HashMap<Integer, Integer> nH = new HashMap<>();
		int sum = 0;
		nH.put(0, 1);
		for(int x : nums){
			sum += x;
			if(nH.containsKey(sum-m)) answer += nH.get(sum-m);
			nH.put(sum, nH.getOrDefault(sum, 0) + 1);
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{2, 2, 3, -1, -1, -1, 3, 2, 1}, 5));	
		System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2, 2, -3}, 5));	
		System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2}, 3));	
		System.out.println(T.solution(new int[]{-1, 0, 1}, 0));	
		System.out.println(T.solution(new int[]{-1, -1, -1, 1}, 0));	
	}
}

원리 설명
문제 개념 이해
부분합: 배열의 각 원소를 더해 나가는 누적합입니다.
목표: 특정 값 M이 되는 연속 부분수열의 개수를 찾는 것.
접근 방식
부분합과 해시맵 사용:

부분합을 계산하면서 현재까지의 부분합과 목표값 M을 뺀 값이 이전에 나왔는지 확인합니다.
이전에 나왔던 부분합의 개수를 이용해 부분합이 M이 되는 경우의 수를 빠르게 계산할 수 있습니다.
수학적 배경:

현재 부분합 sum에서 M을 뺀 값 sum - M이 이전에 나왔다면, 그 부분합부터 현재까지의 부분합은 M이 됩니다.
예를 들어, sum[i]가 현재까지의 부분합이고 sum[j]가 이전에 나왔던 부분합이라면, sum[i] - sum[j] = M이 되는 경우를 찾는 것입니다.
구현 원리
변수 초기화:

sum: 현재까지의 부분합을 저장.
nH: 해시맵으로 각 부분합이 몇 번 나왔는지를 저장.
answer: 연속 부분수열의 합이 M이 되는 경우의 수를 저장.
nH.put(0, 1): 초기값으로 0을 넣어 부분합이 M이 되는 경우를 처리.
부분합 계산 및 해시맵 업데이트:

배열의 각 원소를 순회하며 부분합을 업데이트하고, 필요한 경우 해시맵에서 해당 부분합을 검색하여 answer를 증가시킵니다.
현재 부분합 sum에서 M을 뺀 값 sum - M이 해시맵에 있는지 확인합니다.
nH.containsKey(sum - M)이 true라면, 해시맵에서 그 값이 나온 횟수를 answer에 더해줍니다.
현재 부분합 sum을 해시맵에 업데이트합니다.
예제 설명
주어진 예제 [2, 2, 3, -1, -1, -1, 3, 2, 1]와 m = 5를 사용하여 이 원리를 적용하는 과정을 자세히 살펴보겠습니다.

초기 상태:

sum = 0
answer = 0
nH = {0: 1}
첫 번째 원소 (2):

sum = 0 + 2 = 2
nH.containsKey(2 - 5) → nH.containsKey(-3) → false
nH.put(2, 1) → nH = {0: 1, 2: 1}
두 번째 원소 (2):

sum = 2 + 2 = 4
nH.containsKey(4 - 5) → nH.containsKey(-1) → false
nH.put(4, 1) → nH = {0: 1, 2: 1, 4: 1}
세 번째 원소 (3):

sum = 4 + 3 = 7
nH.containsKey(7 - 5) → nH.containsKey(2) → true
answer += nH.get(2) → answer += 1 → answer = 1
nH.put(7, 1) → nH = {0: 1, 2: 1, 4: 1, 7: 1}
네 번째 원소 (-1):

sum = 7 - 1 = 6
nH.containsKey(6 - 5) → nH.containsKey(1) → false
nH.put(6, 1) → nH = {0: 1, 2: 1, 4: 1, 7: 1, 6: 1}
다섯 번째 원소 (-1):

sum = 6 - 1 = 5
nH.containsKey(5 - 5) → nH.containsKey(0) → true
answer += nH.get(0) → answer += 1 → answer = 2
nH.put(5, 1) → nH = {0: 1, 2: 1, 4: 1, 7: 1, 6: 1, 5: 1}
여섯 번째 원소 (-1):

sum = 5 - 1 = 4
nH.containsKey(4 - 5) → nH.containsKey(-1) → false
nH.put(4, 2) → nH = {0: 1, 2: 1, 4: 2, 7: 1, 6: 1, 5: 1}
일곱 번째 원소 (3):

sum = 4 + 3 = 7
nH.containsKey(7 - 5) → nH.containsKey(2) → true
answer += nH.get(2) → answer += 1 → answer = 3
nH.put(7, 2) → nH = {0: 1, 2: 1, 4: 2, 7: 2, 6: 1, 5: 1}
여덟 번째 원소 (2):

sum = 7 + 2 = 9
nH.containsKey(9 - 5) → nH.containsKey(4) → true
answer += nH.get(4) → answer += 2 → answer = 5
nH.put(9, 1) → nH = {0: 1, 2: 1, 4: 2, 7: 2, 6: 1, 5: 1, 9: 1}
아홉 번째 원소 (1):

sum = 9 + 1 = 10
nH.containsKey(10 - 5) → nH.containsKey(5) → true
answer += nH.get(5) → answer += 1 → answer = 6
nH.put(10, 1) → nH = {0: 1, 2: 1, 4: 2, 7: 2, 6: 1, 5: 1, 9: 1, 10: 1}
최종 결과
answer = 6
따라서, 연속 부분수열의 합이 5가 되는 경우는 총 6가지입니다.