(코딩테스트) 백준_2559_수열 (윈도우 슬라이드)

 

 

 

 

초기 내가 제출한 답.

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

public class Main {
    static int[] list;
    static int max = Integer.MIN_VALUE;  //기본 선언 음수 일 수 있으니 

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        list = new int[n];

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

        for (int i = 0; i < n; i++) {
            if (i + k > n) break;
            int sum = 0;
            int j = i;
            while (j < i + k) {
                sum += list[j];
                j++;
            }
            if (max < sum) max = sum;
        }

        System.out.print(max);
    }
}

 

 

 

 

개선된 답 

package codingTest;

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

public class Backjon_2559 {
	static int[] list ;
	static int max;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = 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 < k; i++) sum += arr[i];

		int max = sum;  
		for (int i = k; i < n; i++) { 
		    sum = sum - arr[i - k] + arr[i];  // 슬라이딩 윈도우
		    max = Math.max(max, sum);
		}

		System.out.println(max);

	}

}

 

 

 

회고.

1. 내가 기존에 제출한 답은 계속 모든 값을 더함.

2.개선된 답은 초기 값에 앞 뒤 값만 뺴고 더하고 (윈도우 슬라이드)

3.속도 5배 정도 향상.

4.Math.max() 함수 잊어먹음...

 

 

 

비교 요약

 

항목	초기  코드	슬라이딩 윈도우 방식
시간복잡도	O(n × k)	O(n)
예: n=100,000, k=1,000	100,000,000번 루프	100,000번 루프
대규모 입력 처리 가능 여부	❌ 시간 초과 가능성	✅ 안정적 처리 가능