백준 2559 수열 (Java/자바) 슬라이딩 윈도우

문제출처 :

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

---

 

문제풀이 :

 

2중 for문을 사용하여 구간별 합을 모두 구하고 max 합을 구하는 방식으로 구현하면

최대 N*M의 시간이 소요되기 때문에 시간 초과가 될 수 있다.

 

(이중 for문으로 구현했을시 코드)

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

public class Boj2559_NoSlidingWindow {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String input = br.readLine();
        String[] parts = input.split(" ");
    
        int N = Integer.parseInt(parts[0]); // 숫자 배열 개수
        int M = Integer.parseInt(parts[1]); // 연속되는 숫자 개수
    
        int[] nums = new int[N];
    
        input = br.readLine();
        parts = input.split(" ");
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(parts[i]);
        }
    
        int maxSum = Integer.MIN_VALUE;
    
        // 모든 구간을 일일이 합산
        for (int j = 0; j <= N - M; j++) {
            int sum = 0;
            for (int k = j; k < j + M; k++) {
                sum += nums[k];
            }
            maxSum = Math.max(maxSum, sum);
        }
    
        System.out.println(maxSum);
    }
}

 

 

이 방법대신 '슬라이딩 윈도우' 방법을 사용해

첫 번째 0 ~ M까지 구간의 합 sum 을 구하고,

그 다음부터는 한 원소씩 슬라이딩 해가며 sum을 만들어준뒤 maxSum값과 비교하는 방식으로 구현한다.

 

 

(슬라이딩 윈도우 적용 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class boj2559 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
    
        String input = br.readLine();
        String[] parts = input.split(" ");
    
        int N = Integer.parseInt(parts[0]); // 숫자 배열 개수
        int M = Integer.parseInt(parts[1]); // 연속되는 숫자의 개수
    
        int[] nums = new int[N];
    
        input = br.readLine();
        parts = input.split(" ");
        for (int i=0; i<N; i++) {
            nums[i] = Integer.parseInt(parts[i]);
        }
    
        // 합계산
        // 첫 구간 (0번째 숫자부터 M-1까지의 합)
        int sum = 0;
        int maxSum = 0;

        for(int i = 0; i < M; i++) {
            sum += nums[i];
        }
        maxSum = sum;
        
        // 슬라이딩 윈도우를 통해 max값 비교
        for (int j = M; j < N; j++) {
            sum = sum - nums[j-M] + nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    
        sb.append(maxSum);
        System.out.println(sb);
    
    }

}

 

만약 M = 3, nums가 {0, 1, 2, 3, 4, 5, 6} 인 경우

0,1,2 3개의 합을 구한 후 

그 다음부터는 '이전 합 - 이전 원소 + 현재 원소' 의 방식으로 합을 구하고

maxSum 값과 비교하여 최대 합을 구해주면 된다.