백준 구간 합 구하기 4 11659 js

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

11659번: 구간 합 구하기 4

로직 설명

 

입력 

 

5 3
5 4 3 2 1
1 3
2 4
5 5

 

첫째줄 5 길이의 배열 중에

더해야하는 인덱싱 번호가 3개 주어진다.

5 4 3 2 1 중에

1 3 번째를 다 더해주면 5 4 3 이라서 12

2 4 는 4 3 2 를 더해줘서 9

5 5는 1 이기때문에 1이다.

 

답은 12 9 1

 

틀린 내 코드

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./준/누적합/11659/input.txt";

const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input.shift().split(" ");
const arr = input.shift().split(" ").map(Number);

input.forEach((e) => {
  const [start, end] = e.split(" ");

  let left = start - 1;
  let sum = 0;

  for (let i = left; i < arr.length; i++) {
    if (end <= i) {
      break;
    }
    console.log(arr[left], start, end, i);

    // 5 1 3 0
    // 4 1 3 1
    // 3 1 3 2
    // 12

    // 4 2 4 1
    // 3 2 4 2
    // 2 2 4 3
    // 9

    // 1 5 5 4
    // 1

    sum += arr[left];
    left++;
  }
  console.log(sum, "\n");
});

입력을 forEach 로 돌리면서 start, end 로 나눠주고

 

인덱싱은 0부터인데 start 는 1부터 시작하기 때문에 left 라는 변수에 start-1 을 할당하고

 

for문으로 i는 더해야하는 첫번째 인덱스부터 돌아준다.

1 이면 1부터 2면 2부터 돌것임

 

반복문안에서 필요없이 반복하는 부분을 줄여주기위해

 

end 라는 예를들어서 1, 3 의 입력이면 

end 3 , i 4 처럼 end 는 3이 되는데 i 가 3보다 커질때는 반복문을 나오게 된다.

 

나머지는 그냥 누산해주면 된다.

 

중간에 주석으로 된 부분이 연산 과정이다.

 

시간복잡도가 n*m 이지만 반복문의 탈출구와 m의 반복자체도 m 만큼 도는것이 아니기 때문에

시간에 대해서는 염려하지 않았는데 시간 초과가 떴다.

 

정답코드

 

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);

이 로직은 그냥 미리 더해주고

더해준 값을 인덱싱해서 찾아가는것 뿐이다.

 

내 로직을 반복문 한번으로 하기 위해 로직을 나눴다? 정도로 이해하면 될것같다.