[Algorithm/Java] SWEA 4835번 - 구간합

---

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

---

🔍 문제 풀이

알고리즘 선택

두 가지 방식으로 풀이할 수 있다.

방식	연산 방법	시간복잡도
브루트포스	매번 M개를 새로 더함	O(N×M)
슬라이딩 윈도우	앞 빼고 뒤만 더함	O(N)

• 브루트포스는 모든 구간을 처음부터 다시 더해서 확인함
• 슬라이딩 윈도우는 이전 구간합에서 앞 빼고, 뒤 더해서 한 칸씩 이동하여 계산

문제 도식화

💻 전체 코드

브루트포스

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=t; tc++){

            StringBuilder sb = new StringBuilder();

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int arr[] = new int[n];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            int minSum = Integer.MAX_VALUE;
            int maxSum = Integer.MIN_VALUE;

            for(int i=0; i<= n-m; i++){
                int sum = 0;
                for(int j = i; j <= i+m-1; j++){
                    sum += arr[j];
                }
                minSum = Math.min(minSum, sum);
                maxSum = Math.max(maxSum, sum);
            }

            sb.append(maxSum-minSum);

            System.out.println(sb);
        }
    }
}

슬라이딩 윈도우

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=t; tc++){

            StringBuilder sb = new StringBuilder();

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int arr[] = new int[n];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            int sum = 0;
            for (int i = 0; i < m; i++) {
                sum += arr[i];  // 초기 구간합
            }

            int minSum = sum;
            int maxSum = sum;

            for (int i = m; i < n; i++) {
                sum = sum - arr[i - m] + arr[i];  // 앞 빼고, 뒤 더함
                minSum = Math.min(minSum, sum);
                maxSum = Math.max(maxSum, sum);
            }

            System.out.println(sb);
        }
    }
}