[BaekJoon] #2559 수열

문제이해

이 문제는 정수의 수열과, 구간의 길이 k 가 주어질 때, 해당 수열에서 구간의 길이가 k인 구간합을 모든 경우에 대해 구하고 그 중 가장 큰 값을 반환해야 하는 문제입니다.

문제접근

구간 합 문제이므로, prefixSum을 이용해보았습니다.

누적 합을 구하지 않고도 다르게 풀 수 있을 듯 합니다.

처음 풀었을땐 직전에 풀었던 햄버거 문제 때문에 ( 아무튼 문제 때문에 ~ ) startIdx와 endIdx 값을 min()과 max()를 이용해 인덱스를 벗어나지 않게 상한과 하한을 설정해서 풀었었는데 필요없을 것 같습니다.

그 이유는 햄버거 문제는 p의 위치는 임의의 위치로, 랜덤하게 주어지는거고 우리는 p를 기준으로 주어진 구간 내에서 가장 가까운 위치의 H를 구하는 문제였기 때문에, 그냥 i-k 값 그대로 이용하면 문자열 인덱스를 벗어날 수 있었습니다.

그러나 이 문제는 경우에는 시작인덱스와 끝 인덱스를 직접 설정하여 구간의 길이가 k 인것을 만족하며 prefixSum 의 인덱스를 넘어서지 않게 길이가 k인 window를 밀어가며 인덱스를 설정해주면 되기 때문에 필요없습니다 .

정리하자면 다음과 같습니다.

1. prefixSum 구하기
2. 시작 인덱스를 초기화시켜가며 길이가 k인 구간 합 구하기 (인덱스에 유의)
3. 동시에 최댓값 업데이트하기

1. prefixSum 구하기
   

2. 시작 인덱스를 초기화시켜가며 길이가 k인 구간 합 구하기 (인덱스에 유의)
3. 동시에 최댓값 업데이트하기 **

code

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());  // 연속적인 날짜의 수
        String[] str = br.readLine().split(" ");

        // 구간 합 배열을 위한 prefixSum[] 생성
        int prefixSum[] = new int[n + 1];  // 1부터 계산하기 위해 n+1로 생성
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(str[i - 1]);
        }

        // 최대값을 구하기 위한 변수 초기화
        int max = Integer.MIN_VALUE;

        // 길이가 k인 구간의 합을 가질 수 있는 모든 i에 대해 계산, 동시에 최댓값 update
        // 시작 인덱스의 끝 값은 n-k이다 !
        for (int i = 0; i <= n - k; i++) {
            int startIdx = i;
            int endIdx = i + k;
            // 구간합 계산: prefixSum[endIdx] - prefixSum[startIdx]
            int sum = prefixSum[endIdx] - prefixSum[startIdx];
            // 최대값 갱신
            if (sum > max) {
                max = sum;
            }
        }

        // 결과 출력
        System.out.println(max);
    }
}