[알고리즘] 백준 > #11659. 구간 합 구하기4

오랜만에 낮에 하는 코딩😀

문제링크

백준 #11658. 구간 합 구하기4

풀이방법

보통 구간 합을 구할때 반복문을 이용해 O(n)의 시간복잡도를 갖는다. 이 문제에서는 전처리를 진행해 O(1)에 구간 합을 구할 수 있도록 했다. (물론, 전처리 과정은 O(n)입니다)

pSum이라는 배열에 처음부터 x개 원소의 합을 저장하는 전처리를 진행했다. 구간을 입력받으면 이 배열을 이용해 O(1)으로 계산을 진행할 수 있었다.

코드

import java.util.Scanner;

public class SumOfIntervals {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }

        int[] pSum = new int[n + 1];
        pSum[0] = 0;
        for (int i = 0; i < n; i++) {
            pSum[i + 1] = pSum[i] + array[i];
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();

            int sumOfIntervals = pSum[end] - pSum[start - 1];
            result.append(Integer.toString(sumOfIntervals) + "\n");
        }
        System.out.print(result.toString());
    }
}