[Baekjoon] 2559번: 수열

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

2559번: 수열

문제 설명

정수 배열이 주어졌을 때, 연속적인 합이 가장 큰 값을 출력해야 한다.

연속되는 범위가 2인 경우는 다음과 같다.

이 경우 최댓값은 21이 된다.

 

연속되는 범위가 5인 경우는 다음과 같다.

이 경우 최댓값은 31이 된다.

풀이 방법

포인터 변수를 활용하여 해결할 수 있다. 범위가 5인 경우를 예로 들면 과정은 다음과 같다.

• MAX: 최댓값을 저장해놓기 위한 변수이다.
• sum: 합계를 저장하기 위한 변수이다.
• p: 인덱스 위치를 가리킬 포인터 변수이다.

 

먼저 0부터 K - 1까지의 합을 sum에 저장하고 그 값은 MAX로 대입한다. p는 다음에 더할 인덱스를 가리키고 있다.

준비

이제 연속적인 수열의 합을 구해야 하는데 어떻게 하는 것이 좋을까? 반복문을 돌면서 매번 모든 합을 계산해야 할까? 더 효율적인 방법이 존재한다. 바로 현재 수열의 맨 첫 번째 수를 빼고 다음 인덱스의 값을 더하면 된다. 첫 번째 수의 인덱스는 p - K를 통해 구할 수 있다.

1회전

이렇게 포인터 변수 하나를 둠으로써 불필요한 반복을 엄청나게 줄일 수 있다.

2회전

3회전

4회전

5회전

p가 N까지 도달해 더 이상 탐색할 수가 없으므로 반복을 종료하고 MAX를 출력하면 된다.

 

이렇게 같은 크기로 이동하는 방식을 슬라이딩 윈도우(Sliding Window)라고 한다. 창문을 옆으로 미는 것과 같이 창문 크기는 그대로지만 위치만 이동하는 것이다.

 

코드는 다음과 같다.

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

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

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);

        int[] temparatures =
                Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int p = K;

        int sum = 0;
        for (int i = 0; i < K; i++) {
            sum += temparatures[i];
        }

        int MAX = sum;

        while (p < N) {
            sum -= temparatures[p - K];
            sum += temparatures[p];

            MAX = Math.max(MAX, sum);

            p += 1;
        }

        System.out.print(MAX);
    }
}