[백준] 11659_구간 합 구하기4 - JAVA

구간 합

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

구간 합을 이용하려면 합 배열을 구해야 한다.

합 배열 만들기

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

인덱스	0	1	2	3
A	10	10	10	10
S	10	20	30	40

이런 식으로 합 배열을 만든다. S 배열에 값을 계산해서 저장하는 for문의 변수 초기화는 1부터 시작해야한다.

반응형

구간 합 공식

S[j] - S[i-1]

1부터 3까지의 구간 합을 구한다치면 S[3] - S[1-1]이 된다. 40-10 = 30이 된다. A배열의 값이 모두 10이라 뭔가 헷갈릴 수 있으니 다른 배열로도 계산해보자.

인덱스	0	1	2	3
A	10	16	3	49
S	10	26	29	78

위 배열에서도 1부터 3까지의 합을 구해보자. 78-10 = 68이 된다.

 

백준_11659

11659번: 구간 합 구하기 4

 

코드

• 통과가 된 나의 허접한 코드

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+1];

        for(int i = 1; i <= n; i++) {
            arr[i] = arr[i-1] + sc.nextInt();
        }

        for(int j = 0; j < m; j++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            System.out.println(arr[end] - arr[start-1]);
        }
    }
}

 

• BufferedReader, StringTokenizer를 사용한 코드

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 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]);
        }
    }
}

반응형

 

제출 결과

첫 번째 제출이 BufferedReader와 StringTokenizer를 사용한 코드이고, 두 번째 제출이 내가 작성한 코드이다. 메모리나 시간 면에서 첫 번째 제출이 더 우수하게 나왔다. 일단 큰 차이는 Scanner와 BufferedReader에서 차이가 난다.

Scanner와 BufferedReader

익숙한 Scanner는 다양한 기능이 지원되기 때문에 무겁다보니 속도가 느리다. 반대로 문자열에 최적화 된 BufferedReader의 경우엔 버퍼를 이용해서 입력의 효율을 높이기 때문이 보다 더 빠르다. 다만 String 타입으로만 입력을 받아들여 String 외 다른 타입에 사용할 때는 변환이 추가적으로 필요하다. 그래서 내가 작성한 코드에 BufferedReader를 적용시켜봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int n = Integer.parseInt(strArr[0]);
        int m = Integer.parseInt(strArr[1]);

        int[] arr = new int[n+1];
        strArr = br.readLine().split(" ");
        for(int i = 1; i <= n; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(strArr[i-1]);
        }

        for(int j = 0; j < m; j++) {
            strArr = br.readLine().split(" ");
            int start = Integer.parseInt(strArr[0]);
            int end = Integer.parseInt(strArr[1]);
            System.out.println(arr[end] - arr[start-1]);
        }
    }
}

시간이 줄긴 줄었지만 엄청나게 드라마틱하게 줄진 않았다. 그렇다면 또 다른 부분에서 성능 차이가 난다는 것이다. 그건 바로바로 두 번째 split과 StringTokenizer이다.

반응형

 

split과 StringTokenizer

익숙한 split()은 문자열을 토큰으로 잘라낸 결과를 배열에 담아 반환하고, StringTokenizer는 데이터를 토큰으로 바로바로 잘라서 반환하기 때문에 성능 차이가 난다.

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());

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

        for(int j = 0; j < m; j++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            System.out.println(arr[end] - arr[start-1]);
        }
    }
}

처음 내가 작성했던 코드 시간은 2916ms였다. BufferedReader와 StringTokenizer를 사용하니 1888ms가 나왔다. 무려 1028ms나 차이났다! 앞으로는 BufferedReader와 StringTokenizer를 잘 사용해봐야겠다.