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

 

슬라이딩 윈도우를 활용한 가장 깔끔한 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	private static int N, M, Q, K, X;
    private static int[] arr;
    private 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());
        
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int twoPointerSum = 0;
        for(int i=0; i<X-1; i++) {
        	twoPointerSum += arr[i];
        }
        
        int maxSum = 0;
        int maxCnt = 0;
        for(int i=X-1; i<N;i++) {
        	twoPointerSum += arr[i];
        	if(maxSum < twoPointerSum) {
        		maxSum = twoPointerSum;
        		maxCnt = 1;
        	}
        	else if(maxSum == twoPointerSum) {
        		maxCnt += 1;
        	}
        	maxSum = Math.max(maxSum, twoPointerSum);
        	twoPointerSum -= arr[i - (X - 1)];
        }
        
        if(maxSum == 0) {
        	System.out.println("SAD");
        }else {
        	System.out.println(maxSum);
        	System.out.println(maxCnt);
        }
        
    }
    
}