백준[21921] 블로그
Algorithm

백준[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);
    }
}

'Algorithm' 카테고리의 다른 글

백준[19598] 최소 회의실 개수  (0) 2024.06.06
백준[15661] - 링크와 스타트  (0) 2024.05.27
백준[2529] - 부등호  (0) 2024.05.22
백준[2638] - 치즈  (0) 2024.05.16
백준[2583] - 영역 구하기  (0) 2024.05.15