[BaekJoon] 2143번 두 배열의 합 문제 - (nodejs/javascript)

문제 번호 :  2143번

문제 바로가기 ☞ https://www.acmicpc.net/problem/2143

---

 

<<< 문제 내용 >>>

---

 

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');

const N = input.shift();

const A_Length = input.shift();
let A = input[0].split(' ').map(Number);
input.shift();
const B_Length = input.shift();
let B = input[0].split(' ').map(Number);

const A_sum = [];
for(let i=0; i<A_Length; i++){
    let idx = 0;
    for (let j=i; j<A_Length; j++){
        idx += A[j];
        A_sum.push(idx);
    }
}


const B_sum = {};
for(let i=0; i<B_Length; i++){
    let idx =0;
    for (let j=i; j<B_Length; j++){
        idx += B[j];
        if(idx in B_sum) B_sum[idx] += 1;
        else B_sum[idx] = 1;
    }
}

let cnt = 0;
for(let i=0; i<A_sum.length; i++){
    let target = N-A_sum[i];

    if(target in B_sum) cnt += B_sum[target];
}

console.log(cnt);

* upper, lower bound로 찾는 방법도 있지만, 이 경우 딕셔너리에 추가하면서도 해결이 가능했습니다.

 

그리고 binary_search로 값을 찾는 방법을 처음에 사용했었는데, 자꾸 오답이 나왔습니다.

머리론 이해가 안돼서 질문을 올려보았더니, ' B_sum 에 중복되는 값이 있을 때 그만큼 count가 되지 않는다. ' 였습니다.

 

그래서 다들 upper - lower로 값을 계산하는구나... 싶었습니다.

 

사실 이 문제 전에 피자 문제에서도 이와 같은 문제가 있었습니다.

이걸 이제야 깨닫다니 ㅜㅜ.. 그래도 덕분에 궁금증 + 알고리즘 사용법을 조금 더 자세히 배울 수 있었습니다.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.