[백준] 11659번: 구간 합 구하기 4 (JavaScript)

 

 

---

 

문제

https://www.acmicpc.net/problem/11659

 

 

개념

누적 합

 

 

실행 결과

12
9
1

 

 

 

 

 

구현 코드(JavaScript)

const fs = require('fs');

// 백준 제출용
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 로컬 테스트용
// const filePath =
//   process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
// const input = fs.readFileSync(filePath).toString().trim().split('\n');

// 백준 11659번: 구간 합 구하기 4
const [n, m] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map((i) => +i);
const lines = input.slice(2);

const prefixSum = Array(n + 1).fill(0); // 구간합 배열
prefixSum[0] = arr[0];
for (let start = 1; start < n; start++) {
  prefixSum[start] = prefixSum[start - 1] + arr[start];
}

lines.forEach((line) => {
  const [i, j] = line.split(' ').map((v) => +v);

  // 단일 구간
  if (i === 1) {
    console.log(prefixSum[j - 1]);
  }
  // 여러 구간: prefixSum[j-1] - prefixSum[i-2]
  else {
    console.log(prefixSum[j - 1] - prefixSum[i - 2]);
  }
});

 

 

 

 

코드 설명

맨 처음에는 단순히 반복문으로 sum을 구하는 식으로 구현했는데, 시간초과가 발생했다.

그 이유는 각 반복마다 O(n)의 시간복잡도가 발생하기 때문이다.

 

이를 해결하기 위해 누적 합을 사용했다. 

 

누적 합(Prefix Sum)

누적합은 배열 내 원소의 값이 변하지 않고 그대로 유지될 때, 특정 구간 내 합을 구하는 데 사용할 수 있다.

왜냐하면 배열 내 원소 값이 바뀌지 않는다면, 누적된 합도 바뀌지 않을 것이기 때문이다.

 

따라서 반복문을 돌면서 그때그때 누적 값을 구하기보다, 미리 구간 별 합이 정의된 누적합 배열을 선언해두고, 필요할 때 인덱스를 이용하는 식으로 구현하면 시간복잡도를 훨씬 개선할 수 있다.

 

개선 전

lines.forEach((line) => {
  const [i, j] = line.split(' ').map((v) => +v);
  let sum = []; // 구간합 합배열

  sum[0] = arr[0];
  for (let k = 1; k < n; k++) {
    sum[k] = sum[k - 1] + arr[k];
  }
  ...

 

이런 식으로 주어진 라인 별로 반복문 쿼리를 돌면서 합을 계산하는 경우, 불필요하게 시간복잡도가 증가할 수 있다.

 

 

누적합을 사용해 개선된 후

먼저 1부터 N까지의 배열 내 원소들을 구간별로 누적해둔 합 배열을 따로 선언한다.

이 선언을 쿼리문 밖에서 진행하여, 시간복잡도를 개선할 수 있다.

const prefixSum = Array(n + 1).fill(0); // 구간합 배열
prefixSum[0] = arr[0];
for (let start = 1; start < n; start++) {
  prefixSum[start] = prefixSum[start - 1] + arr[start];
}

 

index 1부터 시작하여, 이전 원소 누적값에서 현재 탐색하고 있는 시점의 배열 원소값을 추가하는 방식으로 구현할 수 있다.

개인적으로 구현 방법이 dp와 비슷하다고 느껴졌다.

 

lines.forEach((line) => {
  const [i, j] = line.split(' ').map((v) => +v);

  // 단일 구간
  if (i === 1) {
    console.log(prefixSum[j - 1]);
  }
  // 여러 구간: prefixSum[j-1] - prefixSum[i-2]
  else {
    console.log(prefixSum[j - 1] - prefixSum[i - 2]);
  }
});

 

구간 시작과 끝 인덱스를 각각 i, j라고 하자.

만약 i가 1이라면 크게 생각할 필요 없이 끝 인덱스만 생각하면 된다.

 

하지만 중간 구간일 경우, 누적합 배열에서 다음과 같이 뺄셈해야 한다.

 

idx	1	2	3	4	5
arr[idx]	5	4	3	2	1
prefixSum	5	9	12	14	15

 

문제에서 주어진 테스트케이스를 생각해보자.

먼저 (1, 3)의 경우 5, 4, 3을 더해서 12가 나와야 한다.

이는 누적합 배열의 3번째 원소인 12와 같다.

 

두번째 테스트케이스는 (2, 4)로, 4+3+2 = 9가 나온다.

이는 prefixSum[4] - prefixSum[1] =  14 - 5 = 9 와 같은 결과이다.

 

마찬가지로 세번째 테스트케이스는 (5, 5)인데, 이는 prefixSum[5]-prefixSum[4] = 15-14 = 1과 같다.

즉, 이를 점화식으로 나타내면 prefixSum[끝 인덱스 - 1] - prefixSum[시작 인덱스 - 1]이라고 할 수 있다.

 

 

---