[백준7453_자바스크립트(javascript)] - 합이 0인 네 정수

🔴 문제

합이 0인 네 정수

🟡 Sol

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

const n = parseInt(inputs[0]);
const A = [], B = [], C = [], D = [];

for (let i = 1; i <= n; i++) {
  const [a, b, c, d] = inputs[i].split(' ').map(Number);
  A.push(a);
  B.push(b);
  C.push(c);
  D.push(d);
}

const map = new Map();

// A와 B의 모든 합을 계산하여 Map에 저장
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const sum = A[i] + B[j];
    map.set(sum, (map.get(sum) || 0) + 1);
  }
}

let ans = 0;

// C와 D의 합의 음수 값을 찾아서 Map에서 횟수를 더함
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const target = -(C[i] + D[j]);
    if (map.has(target)) {
      ans += map.get(target);
    }
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

처음에 A와 B의 배열을 조합해 모든 합을 담은 배열 AB를 만들고, C와 D의 배열을 조합해 모든 합을 담은 배열 CD를 만들어 두 배열로 이분탐색을 수행했으나 시간초과가 나왔다.
로직상 틀린게 없어보여서 질문게시판을 보니 자바스크립트는 이분탐색으로 풀이를 할 경우 시간초과가 발생한다는 내용을 봤다. 아마 정렬할때 너무 큰 시간이 들어서 그런듯

이분탐색 풀이

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

const n = inputs[0];
const A = [];
const B = [];
const C = [];
const D = [];

for (let i = 1; i <= n; i++) {
  const [a, b, c, d] = inputs[i].split(' ').map(BigInt);
  A.push(a);
  B.push(b);
  C.push(c);
  D.push(d);
}

let AB = [];
let CD = [];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    AB.push(A[i] + B[j]);
    CD.push(C[i] + D[j]);
  }
}

AB = AB.sort((a, b) => (a - b >= 0 ? 1 : -1));
CD = CD.sort((a, b) => (a - b >= 0 ? 1 : -1));

let ab = 0;
let cd = n * n - 1;
let ans = 0;
while (ab < n * n && cd >= 0) {
  const sum = AB[ab] + CD[cd];

  if (sum > 0) cd -= 1;
  else if (sum < 0) ab += 1;
  else {
    ans += 1;
    ab += 1;
  }
}

console.log(ans);

따라서 맵으로 풀이했다.
참고로 자바는 이분탐색을 사용해야 되고 맵으로는 시간초과가 난다고 한다....

맵은 비교적 더 간단하다. A와 B의 모든 합을 계산해서 Map배열에 저장한다.
그 후 C와 D의 모든 합의 음수값이 Map배열에 존재하는지 확인하고 그 횟수를 더해주면 된다.

🔵 Ref