[자바] 백준 2559 - 수열 (boj java)

문제 : boj2559

 

  이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다.

 

1. 누적합 (prefix sum)

   prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다.

 

코드1 : github - prefix sum

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

public class Main {
    private void solution() 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+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = arr[i-1]+Integer.parseInt(st.nextToken());
        int max = -10000001;
        for (int i = k; i <= n; i++) {
            int rangeSum = arr[i]-arr[i-k];
            if (max < rangeSum) max = rangeSum;
        }
        System.out.println(max);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

 

2. 슬라이딩 윈도우 (sliding window)

  K크기의 윈도우를 배열의 처음부터 끝까지 진행하면서 윈도우 내의 수의 합을 구한다고 생각해보자.

  이 때, 윈도우가 오른쪽으로 한칸 움직이면 어떻게 하면 될까? 새로 윈도우에 포함되게 된 맨 오른쪽의 값을 더하고, 윈도우에서 빠지게 된 값을 빼주면 그 다음 위치의 합을 구할 수 있게 된다. 따라서 O(N)에 답을 구할 수 있다.

 

코드2 : github - sliding window

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

public class Main {
    private void solution() 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+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());
        int i = 1;
        int sum = 0;
        while (i<=k) sum += arr[i++];
        int max = sum;
        while (i<=n) {
            sum += arr[i]-arr[i-k];
            if (max < sum) max = sum;
            i++;
        }
        System.out.println(max);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

 

3. 투 포인터 (두 포인터, two pointer)

  슬라이딩 윈도우와 개념적으로 동일하다. start, end의 두 개의 포인터를 두자. end=start+k-1이다. 그리고 start와 end 내에 포함된 수를 더한다고 생각하면 된다.

  그리고 배열의 모든 위치에 대해 start와 end를 동시에 우측으로 진행하면 된다. 슬라이딩 윈도우 때와 마찬가지로 새로 end가 가르키게 되는 값을 더하고, start가 가르키는 값을 빼주면 된다. 역시 마찬가지로 O(N)에 답을 구할 수 있다.

 

코드3 : github - two pointer

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

public class Main {
    private void solution() 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+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());
        int sum = 0;
        for (int i = 1; i <= k; i++) sum+=arr[i];
        int max = sum;
        for (int i = k+1, j=1; i <= n; i++, j++) {
            sum+=arr[i]-arr[j];
            if (max < sum) max = sum;
        }
        System.out.println(max);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}