[백준] 11659번 구간 합 구하기4 - 구간 합 / 배열 / BufferedReader / StringToken

문제

 

 

로직

수의 개수 변수 num 선언&입력 받기

횟수 변수 size 선언&입력 받기

 

수를 저장할 배열(numArray) 선언&크기 지정

구간 합을 저장할 배열(sumArray) 선언&크기 지정

결과를 저장할 배열(resultArray) 선언&크기 지정

 

1. 반복문

- 수를 입력 받아 numArray에 저장

- 구간 합을 계산하여 sumArray에 저장

 

2. 반복문

(위의 반복문과 따로 해야 numArray의 구간 합으로 저장한 값에 의해 sumArray값이 변하지 않음)

- numArray에 구간 합을 계산하여 저장

*sumArray는 1, 2, 3의 구간 합을 0, 1, 3으로 저장하고

  numArray는 1, 3, 6으로 저장함

 

3. 반복문 

- 인덱스  변수 a, b선언&입력 받기

- 인덱스 변수에 따라 배열의 결과 값 저장

 

4. 반복문

- 결과값을 줄바꾸며 출력

 

 

My Code

import java.util.Scanner;

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

        int[] numArray = new int[num];
        int[] sumArray = new int[num];
        int[] resultArray = new int[size];

        for (int i = 0; i < num; i++){
            numArray[i] = sc.nextInt();
            if (i==0) sumArray[i] = 0;
            else sumArray[i] = sumArray[i-1] + numArray[i-1];
        }
        for (int i = 0; i < num; i++){
            numArray[i] = sumArray[i] + numArray[i];
        }
        for (int j = 0; j < size; j++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            resultArray[j] = numArray[b-1] - sumArray[a-1];
        }
        for (int j = 0; j < size; j++){
            System.out.println(resultArray[j]);
        }
    }
}

 

 

문제의 핵심 & 알게된 점

문제에 나와있는 인덱스의 함정을 잘 파악해야 한다.

예를 들면 i = 5, j = 5일 떄 인덱스 별로 같은 배열에 대입하면 뺐을 때 1이 아닌 0이 나와 주의해야 한다. 

 

구간 합을 구할 때 0인덱스의 값이 0인 배열이면서 구간 합의 값을 가지는 배열을 만들어야한다고 생각했다.

즉, 배열에 값을 넣지 않으면 0의 값을 가진다는 걸 몰랐다.

그래서 numArray와 sumArray를 구분해서 배열을 만들어서 결과를 계산했다.

- numArray = {5, 9, 12, 14,15} 

- sumArray = {0, 5, 9, 12, 14}

하지만 밑의 참고 코드처럼 0인덱스에 값을 부여하지 않아서

numArray = {0, 5, 9, 12, 14,15}로 만들 수 있었다.

 

Scanner가 아닌 BufferReader을 이용한 이유는 다량의 데이터를 빠르게 처리할 수 있기 때문이다.

시간 제한이 0.5초여서 이 방식이 더 효율적이다.

 

StringTokenizer은 토큰으로 문자열을 구분할 수 있는 클래스다.

StringTokenizer st = new StringTokenizer(문자열, 구분자, true/false);

구분자를 기준으로 문자열을 구분할 때는 true/false로 분리된 문자열에 토큰 포함여부를 결정할 수 있다.

(default는 false)

nextToken(): 객체의 다음 토큰을 반환

이와 같이 문자열을 파싱하는데는 Split메서드도 사용 가능하다.(차이 O)

 

 

 

참고 Code

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 num = Integer.parseInt(stringTokenizer.nextToken());
        int size = Integer.parseInt(stringTokenizer.nextToken());

        int[] numArray = new int[num + 1];
        int[] resultArray = new int[size];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 1; i <= num; i++){
            numArray[i] = numArray[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }

        for (int j = 0; j < size; j++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());
            resultArray[j] = numArray[b] - numArray[a-1];
        }

        for (int j = 0; j < size; j++){
            System.out.println(resultArray[j]);
        }
    }
}

 

 

참고_인프런의 Do it! 알고리즘 코딩테스트 with JAVA

https://jhnyang.tistory.com/entry/JAVA-StringTokenizer-%ED%81%B4%EB%9E%98%EC%8A%A4%EB%A1%9C-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%B6%84%EB%A6%AC%ED%95%98%EA%B8%B0-split-%EB%B9%84%EA%B5%90