[백준 11659번] 구간 합(Java)

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다.

이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 

 

 

 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

 

구간 합을 구하는 공식

- i에서 j까지 구간 합

S[j] - S[i-1]

 

 

---

 

 

003. 구간 합 구하기(백준 11659번)

 

기존 나의 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];
        int[] sArr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();

            if(i==0) sArr[i] = arr[i];
            else sArr[i] = sArr[i-1] + arr[i];
        }

        for(int i=0; i<m; i++) {
            int i_idx = sc.nextInt();
            int j_idx = sc.nextInt();

            if(i_idx == 1) System.out.println(sArr[j_idx-1]);
            else System.out.println(sArr[j_idx-1] - sArr[i_idx-2]);
        }
    }
}

 

질의 개수(M)도 100,000(10만) 개고, 숫자 개수(N)도 100,000(10만) 개 정도 들어올 수 있기 때문에

Scanner 보다는 BufferedReader 사용하는 게 좋다.

 

숫자의 개수가 100,000 개면 int형으로 받기 힘들다.

StringTokenizer를 사용하면 좋다

 

 

BufferedReader 설명 : 빠른 입력을 위해 사용

• 입력 속도가 빠르고, 특히 많은 양의 데이터를 처리할 때 유리하다.
• System.in으로부터 입력을 읽어오며, readLine() 메서드를 사용하여 한 줄 단위로 입력 받을 수 있다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

• BufferedReader는 InputStreamReader와 함께 사용하여 입력 스트림을 문자 스트림으로 변환하고, 그 결과를 버퍼링하여 효율적인 읽기를 제공한다.

 

 

StringTokenizer 설명 : 문자열을 공백 기준으로 나누어 빠르고 토큰화

• 문자열을 공백이나 특정 구분자로 나눌 때 사용된다. 
• nextToken() 메서드를 통해 문자열의 다음 토큰(구분자로 나누어진 부분)을 가져올 수 있다.

StringTokenizer st = new StringTokenizer(br.readLine());

• br.readLine()을 통해 한 줄의 입력을 받고, 이를 공백 기준으로 나누어 StringTokenizer가 처리한다. 이후 nextToken()을 통해 각각의 숫자를 읽어들인다.

 

 

수정된 코드

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        for (int q = 0; q < m; q++) {
            st = new StringTokenizer(br.readLine());
            int i_idx = Integer.parseInt(st.nextToken());
            int j_idx = Integer.parseInt(st.nextToken());

            System.out.println(sArr[j_idx] - sArr[i_idx-1]);
        }
    }
}

 

여기서 보면 st = new StringTokenizer(br.readLine());이 반복되는 걸 볼 수 있는데

각 입력 줄마다 다른 데이터가 들어오기 때문에, 매변 새로운 StringTokenizer로 해당 줄을 처리해야 한다.