[코테]백준 - 11659번 구간 합 구하기 4

문제

문제분석

나는 아래와 같은 단계를 걸쳐 문제를 분석하고 코드를 작성하기로 하였다.

• 숫자의 개수 n은 최대 100,000 이하
• 합의 횟수 M은 최대 100,000 이하
• n * m = 10억, 시간초과 발생
• n번의 연산이 O(n)이 아닌 그 이하가 되도록 알고리즘 선택
• O(1)의 시간복잡도를 달성 할 수 있는 합 배열 사용
• n번 횟수동안 반복문을 수행하면서 누적된 합을 배열 요소로 저장
• 구간 합의 결과를 O(1)의 시간복잡도로 획득 가능
• 생성된 합 배열에서 M번만큼 반복해야하는 구간 수열 i, j을 통해 구간 합 도출
• 공식 : 합 배열[j] - 합 배열[i -1] = 구간 합

중요한 부분은 i가 0이고 j가 100,000일 때 시간복잡도는 O(n)이기 때문에 합 배열을 통해 시간복잡도를 O(1)으로 단축해주는 것 이었다. 물론 M번만큼의 반복을 해야하지만 구간 합의 시간복잡도만 따지고 본다면 O(1)로 훨씬 단축되기 때문이다.

슈도코드

// 숫자의 개수(n) 입력
// 합의 횟수(M) 입력
// n+1의 길이의 합 배열 선언
// 여기서 n+1은 구간 합을 담아야하기 때문에 마지막 요소의 연산을 위하여 길이를 1증가

for(n만큼 반복){
	//합 배열 요소에 구간 합 대입
    //공식 : 합 배열[i] = 합 배열[i-1] + n[i]
}

for(m만큼 반복){
	// 구간 합 시작 인덱스(i) 입력
    // 구간 합 종료 인덱스(j) 입력
    
    // 결과 출력 : 합 배열[j] - 합 배열[i-1]
}

구현코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int n = Integer.valueOf(stringTokenizer.nextToken());
        int m = Integer.valueOf(stringTokenizer.nextToken());
        int[] preSum = new int[n + 1];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + Integer.valueOf(stringTokenizer.nextToken());
        }

        for (int x = 0; x < m; x++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int i = Integer.valueOf(stringTokenizer.nextToken());
            int j = Integer.valueOf(stringTokenizer.nextToken());

            System.out.println(preSum[j] - preSum[i - 1]);
        }
    }
}

부가설명

합 배열을 만드는 공식과 구간 합을 도출하는 방법을 설명하고자 한다.

합 배열 : 합 배열[i] = 합 배열[i-1] + 기존 배열[i]
구간 합 : 합 배열[종료인덱스] - 합 배열[시작인덱스-1]

위의 내용에서 구간 합을 구할 때 시작인덱스 - 1을 하는 이유는 예를 들어 [2, 5]의 구간에 대한 합을 구해야한다면 합 배열[5] - 합 배열[2]를 할 경우 우리가 원하는 답과 다른 답이 도출된다. 이유는 단순하다 2~5까지의 구간 합을 구해야 할 때 0~1을 제외해야하는데 합 배열[2]를 해버리면 0~2까지 빼버리는 꼴이 되는 것이다.
이러한 이유로 합 배열에서 구간 합을 구할 때는 항상 시작인덱스 - 1이 이루어진다고 외우는 것이 편하다.