구간합 배열

• 2차원 배열에서 입력받은 구역의 합을 구하는 문제이다. 질의가 100,000번 이루어지기 때문에 질의마다 합을 구하게되면 시간초과 문제를 피할 수 없게된다. 이럴땐 구간합을 이용하여 문제를 풀 수 있다.

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] arr = new int[N+1][N+1];
        int[][] sum = new int [N+1][N+1];
        // 배열 채우기
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                arr[i][j] = scanner.nextInt();
            }
        }

        //배열합 구하기
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                sum[i][j] = sum[i-1][j] + sum[i][j-1] + arr[i][j] - sum[i-1][j-1];
            }
        }

        for(int i = 0; i < n; i++) {
            // 이제 예시 받고 진행

            int sumNum= 0;

            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();

            sumNum = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

            System.out.println(sumNum);
        }



    }
}

• 그러므로 다음과 같이 구간합 배열을 구한 후 계산 하였는데 시간초과가 떴다. 고민 후 다른 사람의 문제풀이를 보았을 때 차이는 나는 Scanner를 사람들은 Buffer를 사용한다는 것이었다. 그러므로 Buffer 공부 후 다시 코드를 짜기로 하였다.

Buffer

• 현재 보고있는 Do it 코딩테스트 : 자바편 에서는 BufferReader와 StringTokenizer를 사용하고 있었다.

• 선언

BufferReader buffer = new BufferReader(new InputStreamReader(System.in));
StringTokenizer token = new StringTokenizer(buffer.readLine());

• BufferReader로 한 번에 값을 읽어드린 후 읽은 값은 StringTokenizer을 이용하여 변환을 이용하여 저장한다. 하나씩 저장하는 Scanner와 다르게 한 번에 읽어드린다는 점에 차이가 있다. 공백을 기준으로 잘라서 저장하도록 token에 읽은 값을 저장한다.
• 코드 작성 중 readLine()에서 ExceptionIO를 처리해줘야한다고 오류가 떴다. 그러므로 예외처리 코드가 필요하다. 이는 입력이 null인 경우를 대비한 예외처리라한다.

• 받아온 값을 하나씩 Integer로 변환하여 저장할 수 있다.

int N = Integer.parseInt(st.nextToken());

• 2차원 배열에 이용해보기! 하나의 행의 값을 한 번에 받아 한 행씩 채워나가는 방식이다.

for(int i = 1; i <= N; i++) {
	token = new StringTokenizer(buffer.readLine());
    	for(int j = 1; j <= N; j++){
        	A[i][j] = Integer.parseInt(token.nextToken);
        }
    }
}

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


public class Main {
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N+1][N+1];
        int [][] sum = new int[N+1][N+1];

        // 배열 생성
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }


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

        // test
        for(int i = 0; i < n; i++){
            int numSum = 0;
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            numSum = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];

            System.out.println(numSum);
        }


    }
}