[Baekjoon 2559번] 수열 문제 (with 자바) - 투포인터 알고리즘

문제

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

2559번: 수열

 

 

풀이코드 (실패 - 시간초과)

package com.algorithm._10_투포인터;

import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * @Date 2022/04/10
 * @URL https://www.acmicpc.net/problem/2559
 */
public class A2559_수열 {
    static int N;
    static int K;
    static int[] arr;

    public static void main(String[] args) {
        // write your code here
        A2559_수열 main = new A2559_수열();
        main.solution();
    }

    public void solution() {
        input();

        int cnt = 0;

        int start = 1;
        int end = K;
        int max = Integer.MIN_VALUE;

        int totalCnt = 0;

        int currentSum = 0;

        while (end < arr.length) {
            if (cnt == K) {
                // result 셋팅
                totalCnt++;
                max = Math.max(max, currentSum);

                currentSum = 0;
                cnt = 0; // 리셋

                start = totalCnt + 1; // 1부터 시작이므로
            } else {
                currentSum += arr[start];

                if (start == end) {
                    end++;
                }

                start++;

                cnt++; // K 개를 더해야한다.
            }
        }

        System.out.println(max);
    }

    private void input() {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        arr = new int[N + 1]; // 1부터 시작

        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

 

 

풀이코드 (성공 - 투포인터 알고리즘 사용)

package com.algorithm._10_투포인터;

import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * @Date 2022/04/10
 * @URL https://www.acmicpc.net/problem/2559
 */
public class A2559_수열 {
    static int N;
    static int K;
    static int[] arr;

    public static void main(String[] args) {
        // write your code here
        A2559_수열 main = new A2559_수열();
        main.solution();
    }

    public void solution() {
        input();

        /* 처음 k개만큼 합 구하기 */
        int currentSum = IntStream.rangeClosed(1, K)
                .map(i -> arr[i])
                .sum();

        /* 투포인터 로직 수행 */
        int max = currentSum;
        // K + 1 인덱스부터 시작
        // K = 5일때) 위에서 1 ~ 5 까지의 합을 구했고, 그 다음은 2 ~ 6 이므로 (K + 1) 인 6으로 설정한다.
        for (int i = K + 1; i < arr.length; i++) {
            // 현재 step 에서 더해질 마지막 end index 를 더한다.
            // 이전에 구한 1 ~ 5 까지의 합에서 더하고,
            currentSum += arr[i];

            // i 가 6일때 K = 5, 즉, 1 ~ 5까지에서 1에 해당하는 start index 를 뺀다.
            currentSum -= arr[i - K];

            // 최댓값 설정
            max = Math.max(max, currentSum);
        }

        System.out.println(max);

    }

    private void input() {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        arr = new int[N + 1]; // 1부터 시작

        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

 

 

 

투포인터 알고리즘 구현 설명

투포인터 알고리즘의 구현 순서는 아래와 같다.

1) 처음 K개까지의 총합을 구한다.

2) for문으로 아래 규칙의 로직을 수행한다.

 

• K = 5일 경우

(현재 위 코드로는, 배열 arr 은 1부터 시작한다.)
x  3  -2  -4  -9  0  3  7  13  8  -3

[1] 인덱스 1 ~ 5
currentSum 변수에는 위 1)번의 로직을 거쳤으므로 3 + (-2) + (-4) + (-9) + 0 = -12 값이 저장되어있다.

[2] 인덱스 2 ~ 6
그 다음으로 구해야하는건 (-2) + (-4) + (-9) + 0 + 3 = -12 값이다.

이는 [1]번에서 구한 (-12) 에서 마지막 인덱스 6에 해당하는 arr[6]의 값을 더한다. -> (-12) + (3) = -9
그리고 이전 인덱스 1 ~ 5에서 첫번째 인덱스 1에 해당하는 arr[1]의 값을 뺀다. -> (-9) - (3) = -12 

 

• 2)번 에 해당하는 코드

...
    /* 투포인터 로직 수행 */
    int max = currentSum;
    // K + 1 인덱스부터 시작
    // K = 5일때) 위에서 1 ~ 5 까지의 합을 구했고, 그 다음은 2 ~ 6 이므로 (K + 1) 인 6으로 설정한다.
    for (int i = K + 1; i < arr.length; i++) {
        // 현재 step 에서 더해질 마지막 end index 를 더한다.
        // 이전에 구한 1 ~ 5 까지의 합에서 더하고,
        currentSum += arr[i];

        // i 가 6일때 K = 5, 즉, 1 ~ 5까지에서 1에 해당하는 start index 를 뺀다.
        currentSum -= arr[i - K];

        // 최댓값 설정
        max = Math.max(max, currentSum);
    }
....

 

아래의 구현 로직을 생각해야한다

 

1) i가 K + 1부터 시작한다.

2) 현재 step이 인덱스가 2 ~ 6일 경우 6에 해당하는 값을 이전 step 에 수행되었던 값에서 더한다.

currentSum += arr[i];

 

3) 이전 step의 start index 값은 arr[i - K]로 구할 수 있다. 

i 가 6일 경우, 6 -5 = 1 로 이전 Step의 1 ~ 5 의 start Index인 1과 동일하다.
i 가 7일 경우, 7 - 5 = 2로 이전 Step의 2 ~ 6의 start index인 2와 동일하다.

 

4) 이전 step 1 ~ 5에서 인덱스 1에 해당하는 값을 뺀다.

currentSum -= arr[i - K];