99클럽 코테 스터디 5일자 TIL [04/04]

참여 난이도

자바/미들러

오늘의 문제

백준 2559 수열

문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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 maxSum = sum;
        for (int i = k; i < n; i++) {
            sum = sum - arr[i - k] + arr[i];
            maxSum = Math.max(maxSum, sum);
        }
        System.out.println(maxSum);
    }
}

 

슬라이딩 윈도우 방식을 통해 기능을 구현하였습니다.

 

1. 처음 k개의 합 구하기 (초기 윈도우)

int sum = 0;
for (int i = 0; i < k; i++) {
    sum += arr[i];
}
int maxSum = sum;

 

2. 슬라이딩 윈도우 적용

for (int i = k; i < n; i++) {
    sum = sum - arr[i - k] + arr[i];  // 이전 구간에서 빠지고 새로 들어오는 값
    maxSum = Math.max(maxSum, sum);   // 최대값 업데이트
}

 

처음 생각했을 때는 while 반복문으로 부분합을 구해서 최댓값을 찾아야겠다는 방식으로 다음과 같이 풀이를 하였습니다.

public class Main {
    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 ans = Integer.MIN_VALUE;

        int sIndex = 0;
        int eIndex = sIndex + k - 1;

        while (sIndex < n && eIndex < n) {
            int sum = 0;
            for(int i = sIndex; i <= eIndex; i++) {
                sum += arr[i];
            }
            ans = Math.max(ans, sum);
            sIndex++;
            eIndex++;
        }
        System.out.println(ans);
    }
}

 

시간복잡도가 O(nk)로 통과 자체는 할 수 있었으나 시간 자체가 거의 8배 정도 더 걸리는 것을 확인할 수 있었습니다.