7453 합이 0인 네정수

문제

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

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

====

문제 풀이

처음에는 a+b+c+d =0 이므로 a+b = -(c+d)를 만족하는 경우를 구하면 되지 않을까 싶었지만 

이럴 경우 a+b를 구하는 N^2 이후 이 요소들을 하나씩 끄집어내면서 c+d를 구할려면 N^2*LogN ~ N^3이 되어서 시간 초과가 발생한다. 

그래서 a+b를 담은 ab 배열과 c+d 를 담은 cd배열을 둔 뒤

ab를 탐색하는 left와 cd를 탐색하는 right를 두고 둘의 합이 0이면 answer 값 증가,

0보다 작다면 left++ , 크다면 right--을 해줬다.

만약 0이라면 중복되는 요소또한 처리해주어서 계산 최소화 함

그런데 자바스크립트로 제출하면 시간초과가 계속 발생하고 파이썬으로 제출하면 통과가 됨.

자바스크립트

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

const n = +input[0];
const arr = input.slice(1).map((s) => s.split(' ').map(BigInt));

const AB = [];
const CD = [];

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

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

let left = 0;
let right = CD.length - 1;
let answer = 0n;

while (left < AB.length && right >= 0) {
    const sum = AB[left] + CD[right];
    if (sum === 0n) {
        const abVal = AB[left];
        const cdVal = CD[right];
        let countA = 0n;
        let countB = 0n;

        while (left < AB.length && AB[left] === abVal) {
            countA++;
            left++;
        }

        while (right >= 0 && CD[right] === cdVal) {
            countB++;
            right--;
        }

        answer += countA * countB;
    } else if (sum < 0n) {
        left++;
    } else {
        right--;
    }
}

console.log(answer.toString());

 

파이썬 (정답코드)

import sys


input = sys.stdin.read().strip().split('\n')
n = int(input[0])
arr = [list(map(int, line.split())) for line in input[1:]]

AB = []
CD = []

for i in range(n):
    for j in range(n):
        AB.append(arr[i][0] + arr[j][1])  # A + B
        CD.append(arr[i][2] + arr[j][3])  # C + D

AB.sort()
CD.sort()

left = 0
right = len(CD) - 1
answer = 0

while left < len(AB) and right >= 0:
    sum_val = AB[left] + CD[right]
    if sum_val == 0:
        ab_val = AB[left]
        cd_val = CD[right]
        count_a = 0
        count_b = 0

        while left < len(AB) and AB[left] == ab_val:
            count_a += 1
            left += 1

        while right >= 0 and CD[right] == cd_val:
            count_b += 1
            right -= 1

        answer += count_a * count_b
    elif sum_val < 0:
        left += 1
    else:
        right -= 1

print(answer)

 

 

 

SYS 가져 오기

입력 = sys.stdin.read
data = input (). strip (). split ( '\ n')

n = int (데이터 [0])
arr = [list (map (int, line.split ())) 데이터 [1 :]]

ab = []
C = []
d = []

범위 (n)의 i를 위해 :
범위 (n)의 J의 경우 :
Ab.Append (ARR [I] [0] + ARR [J] [1])

범위 (n)의 i를 위해 :
c.append (arr [i] [2])

범위 (n)의 J의 경우 :
D.Append (ARR [J] [3])

ab.sort ()
c.sort ()
d.sort ()

답 = 0

AB의 목표 :
s = 0
e = n -1
s <n 및 e> = 0 :
sum_cd = c [s] + d [e]
SUM_CD == -TARGET 인 경우 :
c_val = c [s]
d_val = d [e]
count_c = 0
count_d = 0
S <N 및 C [S] == C_VAL :
count_c += 1
s += 1
e> = 0이고 d [e] == d_val :
count_d += 1
e- = 1
대답 += count_c * count_d
elif sum_cd <-target :
s += 1
또 다른:
e- = 1

인쇄 (답변)