[Java] 구간 합 구하기4 - 누적 합 (Lv. Sliver3)

구간 합 구하기4 - 누적 합 (Lv. Sliver3)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

- 코드 해설

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

public class Main {
    static int N, M;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[N+1];
        for (int i = 1; i <= N; i++) {       
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.println(arr[b] - arr[a-1]);
        }
    }
}

 

N+1개의 배열을 만들어주면 모든 원소가 0으로 초기화 됩니다.

누적합을 계산할 때 arr[0]은 0이기 때문에 별도로 초기화하지 않고 arr[1]부터 사용할 수 있 습니다.

 

arr[i] = arr[i-1] + Integer.parseInt(st.nextToken()); 코드가 실행되고 5 4 3 2 1를 입력한다면

i	arr[i]
0	0
1	5
2	9
3	12
4	14
5	15

 

위와 같이 값이 들어가게 됩니다.

 

그 다음에 a구간과 b구간 인덱스를 받아서 b인덱스 값까지의 합에서 a인덱스 값까지의 합을 빼주면 a와 b 구간의 합을 구할 수 있습니다.

arr[b]는 1부터 b까지의 합이기 때문에 1부터 a-1까지의 합을 빼면 a와 b 구간의 합만 남게 됩니다.

 

- 성능 최적화 해설

코드 해설에서의 코드는 1576ms가 걸렸습니다. 여기에서 조금 더 빠르게 출력할 수 있는 방법을 찾아보았습니다.

 

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

public class Main {
    static int N, M;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(arr[b] - arr[a - 1]).append("\n");
        }

        System.out.print(sb.toString());
    }
}

 

위의 코드는 536ms가 걸렸습니다. 기존 코드에서는 출력을 반복 호출하여 출력 비용이 많이 발생했습니다. StringBuilder를 사용하여문자열을 한 번에 출력하면서 I/O 성능을 개선하였습니다. 결과적으로 66%의 성능 향상을 확인할 수 있었습니다.

 

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3