Do it 코딩 테스트: 구간 합 구하기

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

(난이도: 실버 III)

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

 

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

 

 

 

- 문제 분석

그렇다면 이 문제에서 해결해야 할 task는 무엇일까요? 바로

1. 숫자의 수, 구간 합 범위 지정 횟수, 배열 숫자 입력받기

2. 1번에서 입력 받은 배열을 기반으로 누적합 배열 s 만들기

3.  1번에서 입력 받은 구간 합 범위 지정 횟수만큼 돌면서 "범위"(인덱스)를 입력 받아 그 사이의 누적합 구하기

 

이 세가지가 이 문제에서 해결해야 할 task가 될 것 입니다.

 

 

 

 

예를 들어서 한 번 구체적으로 살펴보겠습니다.

입력 예시

 

 

아래와 같은 입력이 들어온다고 가정할게요. 이미지에도 나와 있지만

첫 번째 줄에는 입력받을 숫자의 수와 몇 번 구간 합을 구할건지를 입력받고 있고,

두 번째 줄에는 배열에 담을 숫자들을 입력받습니다.

 

 

구간 합을 구하는 방법

배열을 입력 받았으면 위 이미지의 맨 위 배열처럼 표현될 수 있겠죠? 그 배열을 기반으로 가장 앞부터 차례대로 누적 합을 구하는겁니다. 예를 들어, 입력 배열의 두 번째 즉 arr[ 1 ]까지의 누적 합을 구하고 싶으면 1 + 2가 s[ i ]의 값으로 들어가게 되는거죠. 그래서 위와 같은 합 배열 공식이 성립 할 수 있는거구요. 

 

 이후 누적 합 범위 i, j를 입력 받아서 s [ j ]에서 i의 바로 이전 인덱스인 i-1의 요소 즉 s [i-1] 를 빼면 그 구간의 누적 합이 나오게 될 것입니다!  

-  코드구현

코드 구현 한 번 살펴 볼까요?

주석에 달려있는 1 2 3 표시는 위에 언급 했던 3가지 task와 대응되는 부분이며,

위 문제 분석에서 언급한 구간 합 범위 i, j는 start와 end로 표현하였습니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //1. 문제의 조건에 따라 배열 크기, 구간합을 구하는 횟수 입력 받기
        System.out.printf("입력받을 숫자의 수와 범위지정 횟수: ");
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt(); //java의 nextInt는 공백이나 개행문자를 기준으로 int형 숫자 하나만 받아들임
        int num2 = sc.nextInt();
        
        //1. 문제의 조건에 따라 배열 값들 입력 받기
        int[] arr = new int[num1];
        for(int i = 0; i < num1; i++)
            arr[i] = sc.nextInt();

        //2. 배열 arr의 누적합을 담고 있는 배열 s 구하기
        int[] s = new int[num1];
        for(int i = 0;i < num1;i++) {
            if(i == 0)
                s[i] = arr[i];
            else
                s[i] = s[i-1]+arr[i];

        }
        
        //3. 구간합을 구하는 횟수만큼 돌면서 구간합 구하기
        int start,end;
        for(int i = 0; i < num2;i++) {
            System.out.printf("start end: ");
            start = sc.nextInt();
            end = sc.nextInt();
            if(start == 1)
                System.out.printf("%d부터 %d까지의 구간합은?: %d\n",start,end,s[end-1]);
            else
                System.out.printf("%d부터 %d까지의 구간합은?: %d\n",start,end,s[end-1]-s[start-2]);

        }

    }
}

 

출력 화면은 다음과 같습니다.

 

출력 결과

 

잘 나오죠? 오늘 코딩테스트 마무리 하겠습니다 :)