[알고리즘] 슬라이딩 윈도우

/* 슬라이딩 윈도우 */

슬라이딩 윈도우는 전체 데이터에서 특정 구간의 값을 지속적으로 계산하는 문제에서 사용됩니다. 구간의 시작과 끝을 조정하며 데이터 처리를 최소화해 효율성을 높입니다.

작동 방식

1. 처음에 윈도우 내 데이터를 모두 처리해 초기 값을 계산합니다.
2. 이후 윈도우를 한 칸씩 이동하며, 새로 들어오는 데이터를 추가하고, 이전 데이터를 제거합니다.
3. 반복적으로 윈도우를 이동하면서 원하는 값을 갱신합니다.

/* 슬라이딩 윈도우의 장점 */

• 효율성: 중복 계산을 방지하며, 연속된 구간에 대해 데이터를 재활용하여 O(n)의 시간복잡도를 가질 수 있습니다.
• 간결성: 문제를 단순화하고 가독성을 높이는 코드 작성이 가능합니다.
• 다양한 활용: 배열, 문자열, 또는 다른 선형 데이터에서 부분합, 최댓값, 최솟값, 특정 패턴 탐색 등 다양한 문제에 응용 가능합니다.

/* 고정 크기 윈도우 */

// 배열에서 연속된 k개의 숫자의 합 계산.

public int maxSum(int[] arr, int k) {
    int n = arr.length;
    int maxSum = 0;
    int windowSum = 0;

    // 첫 윈도우 합 계산
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // 슬라이딩 윈도우
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

 

/* 가변 크기 윈도우 */

// 배열에서 합이 특정 값 이상이 되는 가장 작은 윈도우 크기
public int minWindowSize(int[] arr, int target) {
    int n = arr.length;
    int minLength = Integer.MAX_VALUE;
    int windowSum = 0;
    int left = 0;

    for (int right = 0; right < n; right++) {
        windowSum += arr[right];

        // 윈도우의 합이 목표를 초과하면 크기를 줄임
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= arr[left++];
        }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

 

/* 프로그래머스 연속 부분 수열 합의 개수 */

public int circularSubarraySums(int[] elements) {
    Set<Integer> uniqueSums = new HashSet<>();
    int n = elements.length;

    for (int length = 1; length <= n; length++) {
        int sum = 0;

        // 첫 번째 부분합 계산
        for (int i = 0; i < length; i++) {
            sum += elements[i];
        }
        uniqueSums.add(sum);

        // 슬라이딩 윈도우로 나머지 부분합 계산
        for (int start = 1; start < n; start++) {
            sum -= elements[(start - 1) % n];
            sum += elements[(start + length - 1) % n];
            uniqueSums.add(sum);
        }
    }

    return uniqueSums.size();
}