백준[21921] 블로그

• 문제: https://www.acmicpc.net/problem/21921
• 분류: 누적합, 슬라이딩 윈도우
• 난이도: S3
• 소요시간: 10m
• 자아성찰:
  • 특정 배열구간의 합 관련 문제에서 효율적인 풀이 (= 구간합, 슬라이딩 윈도우)를 복습하고자 선택한 문제
  • 문제에서 주어진 배열의 최대 길이, 구간 길이는 250000
    • 이중 for문을 통한 처리 시 O(N^2)로 오랜 시간이 걸림
  • 누적합(Prefix Sum)을 통해 구하는 방식
    • a ~ b 구간합 = prefixSum[b] - prefixSum[a - 1]
  • 슬라이딩 윈도우(Sliding Window)를 통해 구하는 방식
    • 구간 크기가 X일 때 
    • 1 ~ X 합 최초 초기화
    • 이후 위치 i를 증가시키며 현재 윈도우 값 -  [i - X]번째 값 (맨 앞의 값) +  [i]번째 값 (새로운 값)
  • 두 방식을 이용하면 시간복잡도는 O(N)으로 풀이가 가능하다.

---

누적합 (Prefix Sum) - 372ms

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_21921_prefix_sum {
    static int N, X;
    static int[] prefixSum;
    static int max, day = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        prefixSum = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        // 누적합 배열 초기화
        // i번째 구간합 = 1 ~ i까지의 합 = i - 1번째 구간합 + i번째 값
        for (int i = 1; i <= N; i++) {
            prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(st.nextToken());
        }
        // 1 ~ X 합 최댓값으로 초기화
        max = prefixSum[X];
        // 구간합 이용, i번째 ~ i + X - 1번째 구간합 계산
        // a ~ b까지 구간합 = prefix[b] - prefix[a - 1]
        for (int i = 2; i <= N - X + 1; i++) {
            int cur = prefixSum[i + X - 1] - prefixSum[i - 1];
            if (cur > max) {
                max = cur;
                day = 1;
            } else if (cur == max){
                day++;
            }
        }
        System.out.println(max == 0 ? "SAD" : max);
        if (max > 0) System.out.println(day);
    }
}

 

 

슬라이딩 윈도우 (Sliding Window) - 368ms

 

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_21921_sliding_window {
    static int N, X;
    static int[] arr;
    static int max, window, day = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 최초 윈도우 값 설정 (0 ~ X 합)
        for (int i = 0; i < X; i++) {
            max += arr[i];
            window += arr[i];
        }
        // 슬라이딩 윈도우 이용, 한 칸씩 윈도우 이동
        // 현재 윈도우 = 현재 윈도우 - 현재 윈도우 맨 첫번째 방문자수 + i일 방문자수
        for (int i = X; i < N; i++) {
            window -= arr[i - X];
            window += arr[i];
            if (window > max) {
                max = window;
                day = 1;
            } else if (window == max) {
                day++;
            }
        }
        System.out.println(max == 0 ? "SAD" : max);
        if (max > 0) System.out.println(day);
    }
}