[백준] 11659번 문제 구간 합 구하기 4 - JAVA

백준 11659번 문제

 

백준 11659번 문제 예제 입출력

 

 

구간합을 구하는 핵심 문제이다. 구간합이란 정수가 들어있는 배열 A가 있다고 가정했을때, A배열의 i번재 수에서 j번째 수의 합을 구하는 공식이다.

 

구간합을 사용하지 않으면 배열 A를 모두 탐색하면서 해당 구간에서 합 연산을 해야하므로, O(n)의 시간복잡도를 가지지만, 구간합을 사용한다면, 이미 만들어진 합배열 S를 이용하여 구간합을 구하므로, 시간복잡도는 O(1)로 감소한다.
(즉 성능이 좋아진다는 얘기!)

 

이러한 이유로 코딩테스트에서 구간합을 구해야하는 로직이 있다면 시간 복잡도를 줄일 수 있으므로, 많이 사용되는 알고리즘이다.

 

먼저, 합배열 S와 구간합을 구하는 공식을 알아보자.

public class PrefixSumEx{
    public static void main(String[] args){
        // A 배열
        int[] A = {0, 5, 4, 3, 2, 1};
        
        // 합 배열 S
        // 연산 후 배열 S = {0, 5, 9. 12, 14, 15}
        S[0] = A[0];
        for(int i = 1; i < A.length; i++){
            S[i] = S[i - 1] + A[i];
        }
        
        // A 배열의 1번째에서 3번째까지의 수의 합
        // 출력결과 : 12
        System.out.println(S[j] - S[i - 1]);
    }
}

 

※ 여기서 주의할점!

A 배열을 만들때, A[0] 값을 0으로 넣고, 그 다음 주어진 수를 넣어야한다. 즉, 주어진 수의 +1 만큼 크기의 배열이어야한다.
만약, 5개의 수가 주어진 배열 A에서 1번째에서 5번째까지의 수를 구간합 해야한다면

 

※ A[0]에 0을 넣지 않은 경우

//1번째에서 5번째까지의 수를 구간합
int[] A = {5, 4, 3, 2, 1};
// 합배열 S
int[] S = {5, 9, 12, 14, 15};
// 구간합 -> 마지막 수를 참조할때 S[5] 부분에서 예외가 발생!
int result = S[5] - S[1 - 1]; // <- Array Index Out of Bounds Excepion!

//1번째에서 5번째까지의 수를 구간합
int[] A = {5, 4, 3, 2, 1};
// 합배열 S
int[] S = {5, 9, 12, 14, 15};
// 구간합 -> 그렇다고 해서 구간합 공식에 -1씩 한다면..? 마지막 수를 참조할때의 예외는 해결되지만..
int result = S[5 - 1] - S[1 - 2]; // <- Array Index Out of Bounds Excepion!

 

※ A[0]에 0을 넣은 경우

// 1번째에서 5번째까지의 수를 구간합 -> 5 + 4 + 3 + 2 + 1 = 15
int[] A = {0, 5, 4, 3, 2, 1};
// 합배열 S
int[] S = {0, 5, 9, 12, 14, 15};
// 구간합
int result = S[5] - S[1 - 1]; // S[5] = 15, S[0] = 0; ==> 출력 : 15

 

 

정답코드

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

public class Main {
    public static int[] twoPointer(int[] A, int[][] command){

        int[] copyA = new int[A.length + 1];
        int[] answer = new int[command.length];

        copyA[0] = 0;
        for(int i = 1; i < copyA.length; i++){
            copyA[i] = A[i - 1];
        }

        // 합배열 S 구하기
        int[] S = new int[copyA.length];
        S[0] = copyA[0];
        for(int i = 1; i < copyA.length; i++){
            S[i] = S[i - 1] + copyA[i];
        }

        // 구간합 구하기
        for(int t = 0; t < command.length; t++){
            int i = command[t][0];
            int j = command[t][1];

            answer[t] = S[j] - S[i - 1];
        }

        return answer;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < arr.length; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[][] command = new int[M][2];

        for(int x = 0; x < command.length; x++){
            st = new StringTokenizer(br.readLine());
            for(int y = 0; y < command[y].length; y++){
                command[x][y] = Integer.parseInt(st.nextToken());
            }
        }

        int[] result = twoPointer(arr, command);

        for (int i : result) {
            System.out.println(i);
        }
    }
}