구간의 합 구하기

목차

1. 풀이과정

1) 문제

백준 11659번 구간합구하기 : https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

2) 풀이

시간 초과 로직

import java.util.Scanner;

public class 구간합구하기_시간초과 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] numbers = new int[N];

        for(int i = 0; i < N; i++) {
            numbers[i] = sc.nextInt();
        }

        for(int k = 0; k < M; k++) {
            int i = sc.nextInt()-1;
            int j = sc.nextInt();

            int sum = 0;
            for(int index = i; index < j; index++) {
                sum += numbers[index];
            }
            System.out.println(sum);
        }
        sc.close();
    }
}

이 로직내에 이중 for문이 있기때문에 시간복잡도는 O(n²)이다. 문제는 11659번의  제한을 보면 

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

과 같은데 최악의 경우 100,000 * 100,000 = 100억, 즉 100억의 연산을 해야한다. 1억번의 연산이 일반적으로 1초의 시간이 걸린다고 했을 때 100억의 연산은 100초가 걸리는 셈이다. 그리고 11659번 문제의 시간 제한은 1초 이기에 이 로직은 적합한 알고리즘이 아니다. 그렇다면 이 문제에 적합한 알고리즘은 무엇일까? 그 답은 구간 합 알고리즘에 있다.

 

구간 합 

• 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
• 구간 합을 구할려면 합 배열을 먼저 구해야 한다.
  • 배열 A와 합 배열 S 있을 때, 합 배열 S 정의 
  • S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
• 합 배열을 구할 경우 일정 범위의 합을 구하는 시간 복잡도는 O(N)에서 O(1)로 감소한다.
  • 합 배열 S를 만드는 공식 -> S[i] = S[i-1] + A[i]
  • i에서 j까지 구간 합을 구하는 공식 -> S[j] - S[i-1]

예시)

 

- 위 예시에서 2~4 구간합을 구할려면 S[j] - S[i-1] 공식을 활용한다.

- S[4] - S[1] 이 되므로 14 - 5가 되고 정답은 9가 된다. 

 

2. 정답

정답 - 1, Scanner 사용

import java.util.Scanner;

public class 구간합구하기_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] sums = new int[N+1];
        int sum = 0;

        for (int i = 0; i < N; i++) {
            sum += sc.nextInt();
            sums[i+1] = sum;
        }

        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();

            System.out.println(sums[j] - sums[i-1]);
        }
        
        sc.close();
    }
}

 

정답 - 2, BufferedReader, StringTokenizer 사용 

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

public class P11659_구간합구하기 {
    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 k = 0; k < quizNo; k++) {
            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]);
        }

    }
}

BufferedReader와 StringTokenizer사용시 Scanner 사용할 때 보다 로직이 복잡해지지만 Scanner보다 연산이 빨라 연산이 많은 알고리즘에서 많이 쓰이는 클래스이다. 

위 이미지를 보면 아래가 BufferedReader를 사용했을 때, 위가 Scaaner를 사용했을 때 제출결과이다. 사용되는 메모리와 연산 속도가 BufferedReader가 Scanner보다 월등히 나을 걸 알 수 있다.