슬라이딩 윈도우 알고리즘(백준 21921번)

슬라이딩 윈도우

고정된 배열에서 부분 배열들을 활용하여 고정된 폭만큼 움직여 값을 구하는 알고리즘이다.

같은 너비의 연속 구간들의 정보를 활용하는 것이다. 연속된 구간들 속에 정보가 겹치는 부분이 발생하는데 이 부분을 버리지 않고 재활용하는 점이 있다.

예를 들어 1 1 1 1 1 5 1 이라고 배열이 있다고 가정을 한다면 5개의 너비 만큼 한칸씩 이동을 할때 5의 크기중 첫 번째는 제거가 되고 5의 크기 중 우측에 새로 값을 추가해주면 된다. 그러므로 중간에 값이 겹치는 범위는 재활용을 하게 된다.

 

 

https://www.acmicpc.net/problem/21921

21921번: 블로그

 

풀이

1. 슬라이딩 윈도우 범위내(X)만큼의 최대 값을 초기화

2. 범위를 잡는다.(slide_grp = max)

3. X~N만큼 순회하면서 이동한다. 제거 해주면서 값을 추가해준다.(slide_grp -= array[i-X], slide_grp += array[i])

4. 순회시 그룹값과 최대값이 같을 경우 count 증가(slide_grp == max)

5. 만약 최대값 초기화 값이 순회하면서 구한 그룹값보다 작을 경우 그룹값이 최대값이 되면서 count 초기화

코드

public class SlidingWindow {
	public static void main(String[] args) {
		int N1 = 5;
		int X1 = 2;
		int[] array1 = {1, 4, 2, 5, 1};
		solution(N1,X1,array1);
		int N2 = 7;
		int X2 = 5;
		int[] array2 = {1, 1, 1, 1, 1, 5, 1};
		solution(N2,X2,array2);
	}
	public static void solution(int N, int X, int[] array) {
		int max_visit=0;
		int cnt=0;
		// X일동안 첫 슬라이드 최대방문자 값
		for(int i=0; i<X; i++) {
			max_visit += array[i];
		}
		// 첫 값을 최대값으로
		int slide_grp = max_visit;
		// 슬라이딩윈도우 범위X~N
		for(int i = X; i<N; i++) {
			// 그룹의 맨압 제거 그룹의 우측새로운값 추
			slide_grp -= array[i-X];
			slide_grp += array[i];
			if(slide_grp == max_visit) {
				cnt++;
			}else if(slide_grp > max_visit) {
				// 첫값보다 클경우 큰 값을 최대값으로 하고 count초기화
				max_visit = slide_grp;
				cnt = 1;
			}
		}
		if(max_visit == 0) {
			System.out.println("SAD");
		}else {
			System.out.println(max_visit+" "+cnt);
		}
	}
}