정수로 이루어진 크기가 같은 배열 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
인쇄 (답변)
'코딩 테스트 > 백준' 카테고리의 다른 글
20366 같이 눈사람 만들래? (자바스크립트) (0) | 2025.05.26 |
---|---|
2230 수 고르기 (자바스크립트) (0) | 2025.05.23 |
3151 합이 0 (자바스크립트) (0) | 2025.05.22 |
1854 K번째 최단경로 찾기(자바스크립트) (0) | 2025.05.16 |
1800 인터넷 설치 (자바스크립트) (0) | 2025.05.15 |