[Baekjoon] 11659 구간 합 구하기 4 - JAVA

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

---

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

---

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

예제 입력 1 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 

12
9
1

 

---

📝제출 답안

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n+1];
        int[] prefixSum = new int[n+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            prefixSum[i] = prefixSum[i-1] + arr[i];
        }

        for (int k = 0; k < m; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            sb.append(prefixSum[j] - prefixSum[i-1]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

 

처음 문제를 풀었을 때에는 정수형 배열 하나를 선언해 값을 저장해두고

찾고자 하는 i 부터 j 까지의 누적 합을 i-1부터 j까지 for문을 통해 합을 구해 sb에 추가하도록 하였다.

하지만 이렇게 하니까 시간 초과가 떴다.

 

각 요청마다 i-1 부터 j까지의 합을 일일이 계산하면 시간 복잡도가 커질 수 있게 된다.

 

시간복잡도를 줄이기 위해서 누적 합(Prefix Sum) 방식을 사용해야 했다.

미리 배열의 누적 합을 계산해 각 구간 합 요청을 O(1) 의 시간복잡도로 상수 시간 내에 해결할 수 있다.

 

BufferedReader와 BufferedWriter로 각각 입출력을 담당하고, StringBuilder로 문자열을 효율적으로 연결한다.

 

배열의 크기를 n+1로 갖는 입력값을 저장할 배열 arr와 누적 합을 계산해 저장할 배열 prefixSum을 각각 생성한다.

prefixSum[i] = prefixSum[i-1] + arr[i]를 사용해 배열의 1번 인덱스부터 i번 인덱스까지의 합을 저장한다.

한 번의 반복으로 계산하므로 이 부분의 시간 복잡도는 O(n)이다.

 

구간 합[i, j]은 prefixSum[j] - prefixSum[i-1]로 바로 구할 수 있으므로 시간 복잡도는 O(1)이다.

 

전체적으로 이 코드는 평균 O(n) 만큼의 시간복잡도를 통해 효율적으로 구간 합을 구할 수 있다.

 

제출 현황