No11659 구간합 구하기

구간합 문제를 풀기에 압서 배열합과 구간합의 공식과 개념을 먼저 알아볼 필요가 있다.

• 구간합이란 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘
• 구간합 알고리즘을 활용하려면 합 배열을 구해야 한다!
• 합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i]  //A[0]부터 A[i]까지의 합

위 그림에서 S[5]의 값은 A[0] + A[1] + A[2] + A[3] + A[4] + A[5]의 값과 같다.

즉, S[i] = S[i-1] + A[i] 라는 공식까지 도달할 수 있다.

=> S[1] = S[0] + A[1] = 15 + 13 = 28   //   S[5] = S[4] + A[5] = 48 + 12 = 60

 

구간합을 구하는 식도 간편한데 i부터 j까지의 합을 구한다고 할 때, S[j] - S[i-1]로 계산할 수 있다.

=> 1부터 3까지의 합을 구한다고 하면 S[3] - S[0] = 45 - 15 = 30

 

그렇다면 이제 문제를 살펴보도록 하자.

 

[문제]

[조건과 입출력 형식]

 

[문제 이해하기]

먼저 해당 예제를 직접 손으로 그려가면서 이해해봤다. 배열의 크기가 5이고 해당 배열에 5 4 3 2 1이라는 숫자들이 들어가있다고 가정했을 때, 합 배열을 생성하면 S[i] = S[i-1] + A[i]의 공식에 따라 

배열 A : 5   4   3    2    1

배열 S : 5   9   12  14  15

이 만들어질 것이고, 예제의 범위에 따라 구간 합을 구해보면 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

이 나온다는 것을 알 수 있다. 

 

[수도코드 작성]

• N : 숫자 개수, T : 테스트 케이스 횟수, arr[] : 값을 받아올 배열, S[] : 합배열을 생성해줄 배열
• for문을 통해 S[]에 합배열 생성
• for문을 테스트 케이스만큼 돌려서 범위를 받아주고 구간합 공식에 따라서 값 도출

 

[처음 작성한 코드]

public class Main {
    public static void main(String[] args) throws Exception{
        //합배열 S[i] = S[i-1] + A[i]
        //구간합 (i~j) S[j] = S[i-1]
        Scanner st = new Scanner(System.in);

        int N = st.nextInt();
        int[] arr = new int[N+1];
        int[] S = new int[N+1];
        int T = st.nextInt();

	//배열 생성
        for (int i=1;i<=N;i++) {
            arr[i] = st.nextInt();
        }

	//합배열 생성
        for (int i=1;i<=N;i++) {
            S[i] = S[i-1] + arr[i];
        }

	//구간합 구하기
        for(int k=1;k<=T;k++) {
            int i = st.nextInt();
            int j = st.nextInt();
            int result = S[j] - S[i-1];
            System.out.println(result);
        }

    }
}

사실 위 개념만 확실하게 이해가 됐으면 코드를 구현하고 답을 도출해내는건 어렵지 않다. 이 문제가 구간합 문제중에 가장 기초적인 부분이기 때문에 금방 이해할 수 있을 것이다. 그래도 문제를 풀면서 조금 헤맸던 부분은 Scanner를 받지 않고 Buffer로 받을려고 했는데 그 과정에서 조금 버벅거림이 있어서 Scanner로 값들을 받아왔다. 아직 Buffer를 사용하는데 익숙지 않을 것 같아서 해당 부분을 좀 더 공부를 하고 익숙해질 필요가 있다고 생각했다. 일단 위 코드로 제출을 했으나 그리 깔끔한 코드는 아닌 것 같아서 Buffer로 수정하고 배열도 2개가 아니라 1개만 생성해서 다시 코드를 수정해봤다.

 

[최종본]

public class Main {
    public static void main(String[] args) throws Exception{
        //배열의 개수 N, 테스트케이스 T
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //합배열 S[i] = S[i-1] + A[i]
        //구간합 (i~j) S[j] = S[i-1]

        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        long[] S = new long[N+1];
        //해당 문제의 범위도 1부터 100000이였고, 굳이 그렇지 않더라도 실제 코테에서는 범위가 큰 수가 나올 확률이 높으므로 int형으로 범위 안에 해당하는 문제라 하더라도 long타입을 써주는게 안전!

        st = new StringTokenizer(br.readLine());
        for (int i=1;i<=N;i++) {
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());
            //합배열 생성 - 굳이 배열을 2개 쓸 필요없음!
        }

        for(int k=1;k<=T;k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            System.out.println(S[j] - S[i-1]);
        }

    }
}

제일 크게 변한 부분 2가지

1. 스캐너 대신 버퍼를 써준 부분! -> 처음 버퍼를 썼을 때 맘대로 되지 않았던 부분이 StringTokenizer를 사용하는 부분이였는데 처음 N, T의 값을 받아온 이후에 반복문을 통해서 배열 안에 들어갈 값을 받아오는데 5 4 3 이런 식으로 숫자 사이에 spacebar가 들어가있을 때 값을 5만 받아들이고 엔터를 쳐야만 정상적으로 값이 들어오는 문제가 있었다. 자세한 원리는 잘 모르겠으나 토큰나이저를 사용해서 반복문을 쓰거나 엔터를 쳐서 한 섹션이 끝나게 되는 경우에는 토큰나이저를 새로 생성해줘야 하는 원리인 것 같다. 
2. 배열을 한개만 쓴 부분! -> 굳이 배열을 2개 만들어서 초기화 시켜주고 다시 반복문을 통해 합배열을 만드는 것보다 처음부터 하나의 배열만 생성 후 값을 받아오는 동시에 합배열을 만들어주는 부분이 훨씬 빠르다고 생각해서 그렇게 코드를 수정해줬다.

 

[메모리양 비교]

위의 코드가 개선된 코드, 아래 코드가 처음 짰던 코드인데 시간도 절반 가까이 줄어들었고 메모리양은 무려 4배 가까이 줄어든 것을 볼 수 있다! 역시 버퍼가 최고인 것 같다 ^^....