링크텍스트

문제

접근방법

누적합

풀이

💻 내가 짠 코드

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

public class B11659_구간합_송봉섭 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수의 개수
        int count = sc.nextInt(); // 윈도우크기
        int sum =0;
        // 스캐너로 
        

        int[] arr = new int[N]; 
        int[] sumList = new int[N+1];
        sumList[0] = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
            // 5 4 3 2 1 -> 0 5 9 12 14 15
            sum += arr[i];
            sumList[i+1] = sum;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < count; i++) {
            int startIndex = sc.nextInt();
            int lastIndex = sc.nextInt();
            int sub = sumList[lastIndex] - sumList[startIndex-1];
            stringBuilder.append(sub);
            stringBuilder.append("\n");
            sum = 0;
        }
        System.out.println(stringBuilder);

    }
}

arr : 전체 수를 저장하는 배열
sumList : arr[0] | arr[0] + arr[1] | arr[0] + arr[1] + arr[3] ...
이런 식으로 arr 원소 합을 저장하는 배열

• sumList 크기를 [N+1]로 놓았는데 굳이 그럴 필요가 있을까?
  5 4 3 2 1 -> 0 5 9 12 14 15
  5 4 3 2 1 -> 5 9 12 14 15
  이렇게해야 1~3 구간을 구할때 sumList[3] - sumList[1-1] 을 구한다고 생각함

📌 sumList로 배열을 다시 순회하지 않아도 됨!
-> 시간복잡도를 줄이자!

다시풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
	
	
	static int N; // 입력 숫자 갯수 
	static int M; // 구간합 구하는 횟수 
	static int[] S; // 누적합 배열
	static StringBuilder builder;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		builder = new StringBuilder();
		
		String[] str = bf.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		
		S = new int[N+1];
		S[0] = 0;
		
		str = bf.readLine().split(" ");
		
		for (int i = 0; i < N; i++) {
			S[i+1] = Integer.parseInt(str[i]) + S[i];
            // str[i]로 쓰기위해 인덱싱 맞춰줌
		}
        // 배열 초기화 
		
		for (int i = 0; i < M; i++) {
			str = bf.readLine().split(" ");
			int start = Integer.parseInt(str[0]);
			int end = Integer.parseInt(str[1]);
			
			int ans = S[end] - S[start-1]; //처음 , 끝 값이 모두 구간합에 포함되어야함
            //S[end]에는 end에 해당하는 값포함
            //S[start]에는 start에 해당하는 값포함
			builder.append(ans).append('\n');
		}
		System.out.println(builder.toString());
		
	}
}

인덱싱

str = bf.readLine().split(" ");

		for (int i = 0; i < N; i++) {
			S[i+1] = Integer.parseInt(str[i]) + S[i];
            // str[i]로 쓰기위해 인덱싱 맞춰줌
		}
        
        for (int i = 1; i <=N; i++){
        	S[i] = Integer.parseInt(str[i-1]) + S[i-1];
            // 이게 더 직관적이고 헷갈리지 않을 것 같다
        }

최적풀이

package Again;

import java.io.*;
import java.util.*;

class Sol {

    static int N, M;
    static int[] prefixSum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        prefixSum = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        prefixSum[0] = 0;
        for (int i = 1; i <= N; i++) {
            prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            sb.append(prefixSum[end] - prefixSum[start - 1]).append('\n');

        }

        System.out.print(sb);

    }
}