[BOJ/JavaScript] 7453: 합이 0인 네 정수

문제

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

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구해야 한다.

• 1 ≤ 배열의 크기 ≤ 4,000

 

풀이

배열의 최대 크기가 4,000으로 단순 4중 반복문으로는 16,000,000^2번 반복해야 하므로 불가능하다.

이분 탐색 혹은 투 포인터를 활용하거나, 맵으로 저장하는 방법이 있다.

 

처음은 이분 탐색으로 풀이를 시도했는데, 계속 시간 초과가 났다. 그래서 풀이 방법을 찾아보다가 맵을 활용해서 풀었더니 통과할 수 있었다.

찾아보니 JS로는 이분 탐색, 투 포인터로는 시간 내로 풀 수 없다고 한다. 또 자바의 경우엔 맵으로 풀 수 없고, 이분 탐색이나 투 포인터로 풀어야 한다고.

 

코드

const [[n], ...rows] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((line) => line.split(" ").map(Number));

const A = rows.map(row => row[0]);
const B = rows.map(row => row[1]);
const C = rows.map(row => row[2]);
const D = rows.map(row => row[3]);

const ABMap = new Map();

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const sum = A[i] + B[j];
    ABMap.set(sum, (ABMap.get(sum) || 0) + 1);
  }
}

let count = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const sum = C[i] + D[j];
    const target = -sum;
    if (ABMap.has(target)) {
      count += ABMap.get(target);
    }
  }
}

console.log(count);