백준 11659 구간 합 구하기 4 JAVA

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

 

흔한 구간합 구하기 문제인데 나는 딱 구간합 구하기 이론만 아는 상태로 얼레벌레 풀었다

 

구간합 배열을 만들어놓고 2~4 까지의 합이면 4까지의 합에서 1까지의 합을 빼는 방법이다 

 

 

 

제출한코드 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1=0;
        int n2=0;

        int n = sc.nextInt();
        int m = sc.nextInt();
        int A[]= new int[n];
        int S[]= new int[n];

        for (int i =0; i<n; i++){
            A[i] = sc.nextInt();
            if(i==0){
                S[i]= A[i];
            }
            else{
                S[i] = S[i-1]+A[i];
            }
        }

        int R[]= new int[m];
        for (int i = 0; i<m; i++){
            n1 = sc.nextInt()-1;
            n2 = sc.nextInt()-1;
            if (n1 == 0){
                R[i] = S[n2];
            }
            else {
                R[i] = S[n2] - S[n1 - 1];
            }
        }
        for (int i=0;i<m; i++){
            System.out.println(R[i]);
        }

    }
}

 

사실 이 코드에서 A 배열은 구할 필요가 없다.. 왜냐면 S 배열을 만드는데만 사용되기 때문이다

그래서 좀더 최적화 할 수 있다 

그리고 아직 버퍼리더를 많이 안써봐서 스캐너로 풀었는데 버퍼리더가 스캐너보다 빠르기 때문에 버퍼리더 사용도 연습해봐야겠다 

제한된 시간은 만족했지만 채점할때 꽤 오래걸렸다

 

그리고 처음에 배열 입력받는 부분에서 for 문에 i<n이 아니라 i<5를 넣고 길이가 5인 테스트케이스만 시도해보다가 뭐가 문젠지 찾는데 한참걸렸다.

꼭 알고리즘을 풀때는 다양한 테스트케이스 시도해보자