[백준 #2559] 수열

1. 문제 설명

2. 해설

이중 for문을 사용해서 k가 될 때까지 반복해줘도 되지만, 우리는 여기서 '투 포인터' 기법으로 접근해볼 것이다.

💡 투 포인터(Two Pointer)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

위의 예제 중 [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]의 배열에서 연속적인 5개 합을 구하는 경우를 살펴보자.

일반적인 이중 for문을 사용한다면 아마 다음과 같을 것이다.

maxSum = Math.MIN_VALUE;
for (int i = 0; i < length; i++) {
    sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += arr[j];
    }
    maxSum = max(maxSum, sum);
}

하지만 이 방법은 배열의 합을 처음부터 끝까지 모두 구하기 때문에 오래 걸린다는 단점이 있다. 그런데 여기서 투 포인터 기법을 사용하면 어떻게 될까?

int maxSum = Math.MIN_VALUE;
int start = 0, end = 0
int cnt = 1, sum = arr[0]

while (end < length) {
    if (cnt == k) {
        maxSum = max(maxSum, sum);
        --cnt;
        sum -= arr[start++];
    } else {
        ++end;
        if (end < length) {
            sum += arr[end];
        }
        ++cnt;
    }
}    

투 포인터를 사용하면 더한 횟수가 k번째일때 max값을 갱신하고, 앞의 위치 값을 sum에서 빼주면서 불필요한 연산 횟수를 줄일 수 있는 것을 확인할 수 있다.

한 가지 주의하자면 배열 안의 값에 음수도 들어오기 때문에 최댓값이 음수가 될 수 있다. 그래서 maxSum을 int의 최소값(-2^31)으로 초기화해야 한다.

3. 정답 코드

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

public class Main {
    static int[] arr;
    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());

        arr = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(twoPointer(n, k));
    }

    static int twoPointer(int n, int k) {
        int cnt = 1, sum = arr[0], maxSum = Integer.MIN_VALUE;
        int start = 0, end = 0;

        while (end < n) {
            if (cnt == k) {
                maxSum = Math.max(maxSum, sum);
                --cnt;
                sum -= arr[start++];
            } else {
                ++end;
                if (end < n) {
                    sum += arr[end];
                }
                ++cnt;
            }
        }

        return maxSum;
    }
}