[백준] 21921 블로그 - 누적합(Prefix Sum) + 슬라이딩 윈도우(Sliding Window) JAVA

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

21921번: 블로그

코드설명

누적합과 슬라이딩 윈도우 2가지 방법으로 해결할 수 있습니다.

 

유의해야할점은, 투포인터로 슬라이딩 윈도우를 구현한 코드에서 start값 + X 값이 <= N 보다 작을경우로 처리해야합니다.

그렇지 않을경우 ArrayOutofIndex 에러가 나옵니다.

코드

누적합으로 푼 코드

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


public class Main {
	
	public static int N, X;
	public static int[] arr;
	public static int[] prefixSum;
	public static int MaxValue = Integer.MIN_VALUE;
	public static int answer = 0;
    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];
    	prefixSum = new int[N+1];
    	
    	int sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());    		
    		sumValue += arr[i];
    		prefixSum[i+1] = sumValue; 
    	}
    	
    	//각 구간에서 최대값 구하기, -> 쿼리당 계산시간은 O(1)
    	for(int i=0;i<=N-X;i++) {
    		int calculated = prefixSum[i+X] - prefixSum[i];
    		MaxValue = Math.max(MaxValue, calculated);
    	}
    	
    	for(int i=0;i<=N-X;i++) {
    		int calculated = prefixSum[i+X] - prefixSum[i];
    		if(calculated == MaxValue) {
    			answer += 1;
    		}
    	}
    	
    	if(MaxValue == 0) {
    		System.out.println("SAD");
    		return ;
    	}
    	
    	System.out.println(MaxValue);
    	System.out.println(answer);
    }


    
}

 

투포인터로 푼 코드

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


public class Main {
	
	public static int N, X;
	public static int[] arr;
	public static int[] prefixSum;
	public static int MaxValue = Integer.MIN_VALUE;
	public static int answer = 0;
    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];
    	prefixSum = new int[N+1];
    	
    	int sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());    		
    	}
    	
    	twoPointerWithSlidingWindow();


    	if(MaxValue == 0) {
    		System.out.println("SAD");
    		return ;
    	}
    	
    	System.out.println(MaxValue);
    	System.out.println(answer);
    }

    public static void twoPointerWithSlidingWindow() {
    	int start = 0;
    	int end = 0;
    	int intervalSum = 0;
    	
    	// ( start값 + X ) 가 N보다 작거나 같아야 범위를 벗어나지 않습니다.
    	while(start + X <= N) {
    		
    		//end 값과 start값의 차이가 X만큼 차이나게 고정시킵니다.
    		while(start + X > end) {
    			intervalSum += arr[end];
    			end += 1;
    		}
    		
    		if(intervalSum > MaxValue) {
    			MaxValue = intervalSum;
    			answer = 0;
    		}
    		
    		if(intervalSum == MaxValue) {
    			answer += 1;
    		}
    		
    		intervalSum -= arr[start];
    		start += 1;
    	}
    	
    }
    
}