백준, 11659 구간 합 구하기 4 자바스크립트

백준, 11659 구간 합 구하기 4 자바스크립트

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

👨‍💻 문제 풀이

• 나이브한 관점으로 쉽게 생각할 수 있지만 대부분 시간초과가 난다.
• 수의 개수인 N이 100,000까지 올라가고 테스트 케이스도 많은 것 같다.
• 수학적으로 생각하면 i,j 사이의 합은
  - j까지의 합 - i-1까지의 합이다.
• 이를 위해, 처음에 0이 들어갈 수 있도록 해준다.

💻 제출한 코드

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

input.shift();
const map = input.shift().split(' ').map(Number);
const TCs = input.map((item) => item.split(' ').map(Number));

const sumArr = Array.from({length : map.length+1}).fill(0);
map.forEach((v, i) => {
    sumArr[i+1] = sumArr[i] + v;
})

let answer = '';
TCs.forEach((TC) => {
    answer += (sumArr[TC[1]] - sumArr[TC[0]-1]) + '\n';
})
console.log(answer);

이번 문제를 풀면서,

• 백준에서 문제 풀면서 제일 절망적인 순간은 항상 시간 초과 나올때..
• 알고리즘의 기본을 모르고 양치기처럼 문제만 풀고 있으니 시간초과가 나오면 어떻게 고쳐야할지 감이 생기지 않는다.