코딩 테스트 [자료구조] - 구간 합 구하기1

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

---

입력

1번째 줄에 수의 개수 N(1 ⪯ N ⪯ 100,000), 합을 구해야 하는 횟수 M(1 ⪯ M ⪯ 100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와 j가 주어진다.

출력

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

예제 입력
5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력
12
9
1

---

1단계 - 문제 분석하기

문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000회.
구간 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다.
이럴 때 구간 합을 이용.

2단계 - 손으로 풀어 보기

1 N개의 수를 입력받음과 동시에 합 배열을 생성한다.

합 배열 공식
S[i] = S[i-1] + A[i]

인덱스      1  2  3   4   5
배열 A  =   5  4  3   2   1
합 배열 S = 5  9  12  14  15

2 구간 i~j가 주어지면 구간 합을 구하는 공식으로 정답을 출력한다.

구간 합 공식
S[j] - S[i-1]

질의1(1,3) : S[3] - S[0] = 12 - 0 = 12
질의2(2,4) : S[4] - S[1] = 14 - 5 = 9
질의3(5,5) : S[5] - S[4] = 15 - 14 = 1

3단계 - sudo코드 작성하기

suNo(숫자 개수), quizNo(질의 개수) 저장하기
for(숫자 개수만큼 반복하기) {
	합 배열 생성하기(S[i] = S[i-1] + A[i])
}
for(질의 개수만큼 반복하기) {
	질의 범위 받기(i ~ j)
    구간 합 출력하기(S[j] - S[i-1])
}

4단계 - 코드 구현하기

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

public class Q3 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int suNo = Integer.parseInt(stringTokenizer.nextToken());
        int quizNo = Integer.parseInt(stringTokenizer.nextToken());
        long[] S = new long[suNo + 1];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int i = 1; i <= suNo; i++){
            S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }

        for(int q = 0; q < quizNo; q++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int i = Integer.parseInt(stringTokenizer.nextToken());
            int j = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(S[j] - S[i-1]);
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편