[백준] 7453번: 합이 0인 네 정수 (JavaScript)

 

 

---

 

문제

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

 

 

개념

투포인터, 이분탐색, 해시맵

 

 

구현 코드(JavaScript)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input[0];
const lines = input.slice(1).map((li) => li.split(' ').map((i) => +i)); 
const map = new Map();
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const rowSum = lines[i][0] + lines[j][1];
    map.set(rowSum, (map.get(rowSum) || 0) + 1);
  }
}

let count = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const rowSum = lines[i][2] + lines[j][3];
    if (map.has(-rowSum)) {
      count += map.get(-rowSum); // undefined
    }
  }
}

console.log(count);

 

 

 

코드 설명

4개의 열(column)을 가진 n x 4 크기의 행렬이 주어졌을 때 A[a]+B[b]+C[c]+D[d]=0이 되는 쌍, 즉 조합 개수를 찾는 문제입니다.

입력 행마다 4개의 원소가 각각 주어지는데, 여기서 4개가 합쳐서 0이되는 경우의 수를 찾으려면 너무 복잡합니다.

따라서 4개를 2개, 2개로 분리하여 각각 2개의 배열의 합이 0이되는 경우의 수를 찾는다면 좀 더 간단하게 로직을 구현할 수 있습니다.

 

따라서 저는 4개의 배열을 담을 수 있는 배열 하나를 생성해 입력받아놓고, 투포인터로 이분탐색을 진행해 모든 경우의 수를 찾았습니다. 구현 자체는 답이 제대로 나왔지만 백준에서는 시간 초과가 발생했습니다.

 

❌ 오답 코드 일부

const arr = Array.from({ length: 4 }, () => []); // 4개의 배열을 담을 수 있는 2차원 배열 생성
for (let i = 0; i < n; i++) {
  for (let j = 0; j < 4; j++) {
    arr[j].push(lines[i][j]);
  }
}
const ab = [];
const cd = [];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    ab.push(arr[0][i] + arr[1][j]);
    cd.push(arr[2][i] + arr[3][j]);
  }
}
// 투포인터 이분탐색을 위해 정렬
ab.sort((a, b) => a - b);
cd.sort((a, b) => b - a);
let count = 0; // 합이 0이 되는 쌍의 개수
let left = 0;
let right = 0;
while (left < ab.length && right < cd.length) {
  const sum = ab[left] + cd[right];
  if (sum === 0) {
    const lIdx = ab[left];
    const rIdx = cd[right];
    let lCnt = 0;
    let rCount = 0;
    // 카운팅: 동일 값이 존재할때, 중복 값 처리 (조합)
    while (left < ab.length && ab[left] === lIdx) {
      left++;
      lCnt++;
    }
    while (right < cd.length && cd[right] === rIdx) {
      rCount++;
      right++;
    }
    count += lCnt * rCount;
  } else if (sum < 0) {
    left++;
  } else {
    right++;
  }
}
console.log(count);

 

시간 초과 문제는 동일한 값의 쌍이 있을 때, 이를 중복처리하는 데에서 비롯되었습니다.

따라서 해당 문제를 해결하기 위해 먼저 쌍들을 모두 해시맵에 저장하여 중복을 제거해두고, 이 때 동일한 값이 나오는 횟수를 미리 기록해두기로 했습니다. 

 

✅ 개선하기

1. 입력 처리

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input[0];
const lines = input.slice(1).map((li) => li.split(' ').map((i) => +i));

• lines[i] = [A[i], B[i], C[i], D[i]] 형식으로 각 행을 입력받습니다.

2. A[i] + B[j] 합의 모든 경우의 수를 Map에 저장

const map = new Map();
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const rowSum = lines[i][0] + lines[j][1];
    map.set(rowSum, (map.get(rowSum) || 0) + 1);
  }
}

• 모든 (i, j)에 대해 A[i] + B[j]의 합을 계산합니다.
• 이 합을 Map에 저장하면서, 동일한 합이 등장하는 쌍의 개수를 기록합니다. (중복 조합이므로)

3. C[k] + D[l]을 계산하고 -(C[k] + D[l])가 Map에 있는지 확인

let count = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    const rowSum = lines[i][2] + lines[j][3];
    if (map.has(-rowSum)) {
      count += map.get(-rowSum); // undefined
    }
  }
}

• 모든 (i, j)에 대해 C[i] + D[j]를 계산합니다.
• 이 값의 음수 (-rowSum) 가 Map에 존재하는지 확인하여, 존재한다면 count에 해당 쌍의 개수를 더합니다. 
• 0이 되려면 A+B의 합과 절댓값은 같고 부호는 반대여야 하기 때문입니다.

 

 

---