[백준11441-silver3] 합 구하기 (javascript)

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

11441번: 합 구하기

 

 

[풀이]

N 개 요소의 배열 에서 

M 개마다 i, j 누적합을 구하는 문제이다 

 

처음 풀이에서는 시간초과가 났다. 

난이도에 비해 쉽다면,, 무조건 시간초과 나는 문제임을 주의하자!

 

 

 

 

 

✂️시간 초과 나는 문제 

const fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().trim().split('\n'); //[ '5', '10 20 30 40 50', '5', '1 3', '2 4', '3 5', '1 5', '4 4' ]

let n = Number(input[0]);
let m =  Number(input[2]);
let arr = input[1].split(" ").map((el) => +(el)); 
// console.log('🍀',  (input[3]).split(' ').map(el => +el)[0]);
let sumArr = [];
for(let i=0; i < m; i++) {
  let I = (input[i+3]).split(' ').map(el => +el)[0]
  let J = (input[i+3]).split(' ').map(el => +el)[1]
  let sum = 0;

  for(let j=I; j<=J; j++){
    sum += arr[j-1]
  }
  sumArr.push(sum);
  
}
console.log(sumArr.join('\n'));

중첩된 반복문의 시간 복잡도 때문 -> 내부 반복문의 실행 횟수가 배열의 크기에 비례하여 더 많아질수록 실행 시간이 길어짐

 

 

📍 효율적인 알고리즘 

시간 : 392ms

const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().trim().split('\n');

const n = Number(input[0]);
const arr = input[1].split(" ").map(el => +el);

let prefixSum = [];
prefixSum[0] = arr[0];
for (let i = 1; i < n; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
}

const m = Number(input[2]);
let sumArr = [];
for (let i = 0; i < m; i++) {
    const [I, J] = input[i + 3].split(' ').map(el => +el);
    let sum = prefixSum[J - 1] - (prefixSum[I - 2] || 0);
    sumArr.push(sum);
}

console.log(sumArr.join('\n'));

 

누적 합을 사용하여 각 구간의 합을 미리 계산 (필요한 구간의 합을 빨리 조회 -> 시간 단축)

I~J누적합 = 0~J인덱스까지의 누적합 - 0~I인덱스 까지 의 누적합 

 

 

 

 

🔎 Array.prototype.forEach()

: 각 배열 요소에 대해 제공된 함수를 한 번씩 실행

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach

Array.prototype.forEach() - JavaScript | MDN

const array1 = ['a', 'b', 'c'];

array1.forEach((element) => console.log(element));

// Expected output: "a"
// Expected output: "b"
// Expected output: "c"

 

 

🔎 String.prototype.trim()

: 문자열 양 끝 공백 제거후 새로운 문자열 반환

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/trim

String.prototype.trim() - JavaScript | MDN

const greeting = '   Hello world!   ';

console.log(greeting);
// Expected output: "   Hello world!   ";

console.log(greeting.trim());
// Expected output: "Hello world!";