2143 두 배열의 함 (자바스크립트)

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

=====

문제 분석

일단 각 배열에는 -백만부터 백만까지 들어가니까 전체 배열들을 탐색해야한다.

두 개의 배열에서 각각 나올 수 있는 연속 합들을 도출 한 배열를 만든다.

const makeSumArray = (n, array) => {
    const sum = [];

    for (let i = 0; i < n; i++) {
        let s = array[i];
        sum.push(s);
        for (let j = i + 1; j < n; j++) {
            s += array[j];
            sum.push(s);
        }
    }
    return sum;
};


const aSum = makeSumArray(an, arr);
const bSum = makeSumArray(bn, brr);

a에서 나올 수 있는 연속 부분수열의 합들을 순회하면서 t에서 그 밸류를 뺀 값이 bSum에 있는 갯수를 answer에 더해주면 된다.

aSum+bSum =t 니까 t-asum 값을 bSum에서 찾는다는 의미 

그 전에 bSum에는 같은 밸류가 여러개 있을 수 있으므로 Map으로 단일화 한다.

const bSumCount = new Map();
for (const value of bSum) {
    bSumCount.set(value, (bSumCount.get(value) || 0) + 1);
}

이후에는 앞에서 언급한 대로 t-aSum을 하고 bSum (맵) 에서 갯수를 answer에 더해준다.

let answer = 0;
for (const value of aSum) {
    const diff = t - value;
    if (bSumCount.has(diff)) {
        answer += bSumCount.get(diff);
    }
}
console.log(answer);