백준 - 블로그(21921) / 슬라이딩윈도우

⭐ 오늘 풀어본 문제는 블로그 이다.

1. 문제요약

• 블로그 총 기간 N, 특정 기간 X가 주어짐
• X일동안 최대 접속자 수 구하기

2. 알고리즘

2.1 누적합으로 풀기.

1. prefix 배열 생성 (N+1)
2. prefix[i] = prefix[i-1] + 입력값
3. for (end = X end = X ~ N; end++)
4. sum = prefix[end] - prefix[end-X]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[] prefix = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            prefix[i] = prefix[i - 1] + Integer.parseInt(st.nextToken());
        }

        int max = 0;
        int cnt = 0;

        for (int end = X; end <= N; end++) {
            int sum = prefix[end] - prefix[end - X];

            if (sum > max) {
                max = sum;
                cnt = 1;
            } else if (sum == max) {
                cnt++;
            }
        }

        System.out.println(max == 0 ? "SAD" : max+"\n"+cnt);
    }
}

2.2 슬라이딩 윈도우로 풀기

1. 처음 X개 합을 먼저 구해서 windowSum 초기화
2. max = windowSum, cnt = 1로 시작
3. for (right = X ~ N-1)
4. windowSum += arr[right]
5. windowSum -= arr[right-X]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int windowSum = 0;
        for (int i = 0; i < X; i++) {
            windowSum += arr[i];
        }

        int max = windowSum;
        int cnt = 1;

        for (int right = X; right < N; right++) {
            windowSum += arr[right];
            windowSum -= arr[right - X];

            if (windowSum > max) {
                max = windowSum;
                cnt = 1;
            } else if (windowSum == max) {
                cnt++;
            }
        }

         System.out.println(max == 0 ? "SAD" : max+"\n"+cnt);
    }
}

두 알고리즘 차이!

누적합

• 전체 누적합 배열을 만든 뒤
• 구간합을 prefix[end] - prefix[start-1]로 계산

슬라이딩 윈도우

• 첫 구간합을 먼저 만든 뒤
• 다음 구간합은 이전 합에서 앞값을 빼고 뒷값을 더해 갱신

고정 길이 구간 문제에서는 슬라이딩 윈도우가 더 직관적이다.