[백준 알고리즘] Q11441 합 구하기 - Out Of Memory 예외 해결

1. Java 구현

 (1) 메모리 초과 사례 - 이중배열

      
package test;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		String[] input = br.readLine().split(" ");
		int[][] arr = new int[100000 + 1][100000 + 1];
		
		for(int i = 1; i < arr.length; i++) {
			for(int j = i; j < arr[i].length; j++) {
				arr[i][j] = arr[i][j - 1] + Integer.parseInt(input[j - 1]);
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			sb.append(arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]).append("\n");
		}
		
		bw.write(sb.toString());
		bw.close();
	}
}

 (2) 성공 코드

            
package test;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		String[] input = br.readLine().split(" ");
		int[] arr = new int[n + 2];
		for(int i = 1; i < arr.length - 1; i++) {
			arr[i] = arr[i - 1] + Integer.parseInt(input[i - 1]);
		}
		
		int m = Integer.parseInt(br.readLine());
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			sb.append(-arr[Integer.parseInt(st.nextToken()) - 1] + arr[Integer.parseInt(st.nextToken())] + "\n");
		}
		
		bw.write(sb.toString());
		bw.close();
	}


}

2. 코드설명

 첫번째 코드에서는 크기가 100,000 * 100,000 인 이중배열을 생성해서 문제를 풀다보니, 힙 메모리 초과하는 오류가 발생했다.

 arr[1] 에서는 1 ~ n 까지의 자리수 합을, arr[2]에서는 2 ~ n 까지의 자리의 합을 저장할 수 있도록 작성을 했다. 하지만, 오류 발생!

 그래서, 두번째 방법을 통해서 코드를 개선했다. 두번째 방법은 배열에 각 자리수까지의 합을 모두 저장하는 방식이다. 

 예를들자면, 숫자가 10 20 30 40 을 입력받았다고 가정하자!

 arr[1] = 1번째 수까지의 합 = 10 arr[2] = 2번째 수까지의 합 = 30 arr[3] = 3번째 수까지의 합 = 60 arr[4] = 4번째 수까지의 합 = 100

 그래서 2 ~ 3 번째까지의 합은 1 ~ 3 번째 까지의 합에서 1번째자리에서의 합을 뺀것과 같다. 이것을 간단하게 정리하자면, arr[3] - arr[1] 이다.

 그리고 3 ~ 4 번째까지의 합은 1 ~ 4 번째 까지의 합에서 1 ~ 2 번째 자리까지의 합을 뺸것과 같다. 이것을 간단하게 정리하자면 arr[4] - arr[2] 이다.

 위와 같이 풀면 첫번째 방식과는 달리 배열의 크기를 줄일수 있기 때문에 오류가 발생하지 않는다!

3. Pain Point

 입력의 숫자가 큰 방식은 단순하게는 접근을 하지 못하는것 같다. 그리고 힙 메모리 공간도 고려해야 한다는 점이 어려웠다..