[BaekJoon] #11659 구간 합 구하기4

문제이해

이 문제는 구간 합을 구하는 문제입니다.

구간합을 구할 때 일반적으로 배열+이중 for문을 생각 할 수 있습니다.

그러나, 이 문제는 입력값의 범위가 매우 크고, 시간제한이 1초이므로 이를 고려하여 문제를 풀어야 합니다.

이 문제에서 주의해야하는 부분은 데이터의 개수인 M과, 질의 수인 N의 범위입니다.

문제를 풀 때 값의 범위를 보고 언제나 worst case에 대해 생각해봐야 합니다.

---

아무것도 고려하지 않은 채로, 배열과 이중 for문을 이용한다고 생각해봅시다.

worst case

최악의 경우, N과 M 모두 최대 입력값으로 들어와 100,000개의 데이터에 대해서 100,000번의 구간 합 연산을 하는데, 마침 구간도 마법같이 모두 1부터 1000,000 으로 주어진다면..

각 질의에서 100,000개의 원소를 모두 더하는데 100,000번 반복..하면 백억번정도 나올 것 같습니다.

arr[] + for문 Time Complexity

즉, 이중 for문을 이용해 구한다면 $O(N*M)$ 의 time complexity를 갖습니다.

이중 for문을 없애지 못한다면 절대 1초의 실행시간 안에 연산을 끝낼 수 없습니다.

찾아보니 prefixSum을 이용해야 한다고 합니다.

아 약간 메모이제이션 느낌이네! 신기하다!

prefixSum을 이용하면 무려 linear time 으로 줄일 수 있습니다.

prefixSum

• prefixSum은 배열에서 어떤 구간의 합을 빠르게 구하기 위해,아래와 같이 특정 인덱스까지의 누적합을 미리 계산해두는 방법입니다.

prefixSum Time Complexity

• 누적합을 구하는 시간은 $O(N)$입니다.

• 구간 합은 $O(1)$ 의 시간복잡도를 갖는데, 총 M번 질의하므로, 구간 합 연산을 M번 해야합니다.

• 따라서, 총 질의 횟수에 대한 구간합을 구하는데 걸리는 시간은 $O(1)*m = O(M)$ 입니다.

그러므로, prefixSum 을 이용해 구간합을 구하는데에 걸리는 총 time complexity는 $O(N+M)$가 됩니다.

---

prefixSum 을 이용해 구간 합 구하는 과정

• 구간 합은 누적 합 간의 차를 통해 구할 수 있습니다.

• 누적합을 구하기 위해 다음과 같이 1 based index으로 설정해주어야 합니다.

• PrefixSum[i] 는 i번째 인덱스까지의 누적합을 의미하고, i-1까지의 누적합에 arr[i] 원소값을 더해주면 됩니다.

• 구간 합은 누적 합 간의 차를 이용해 구해주면 됩니다.

---

문제접근

입력값 파싱 및 저장

• 입력을 위해 BufferedReader를 사용하였습니다.

• N과 M을 입력받고, 각각의 arr과 prefixSum배열을 생성해주었습니다.

• for문을 통해, 배열에 값들을 저장해주고, 동시에 prefixSum 배열도 초기화해주었습니다.
  

구간 합 계산

prefixSum

• 아래와 같이 for문을 이용해 각각의 질의에 대한 구간합을 누적합 간의 차를 통해 계산하고, Stringbuilder 객체에 append해주었습니다.

틀린 code

배열 + 이중for문

prefix를 사용하지 않는다면 아래와 같이 이중for문이 발생합니다.

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 br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] list = new int[N + 1];
        int[] prefixSum = new int[N + 1];

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

        StringBuilder sb = new StringBuilder();

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

            int sum = prefixSum[b] - prefixSum[a - 1];
            sb.append(sum).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}