BOJ 2470: 두 용액 · English · 日本語
서로 다른 두 용액을 골라 합의 절댓값이 가장 작게 만드는 문제입니다. 용액 값을 정렬한 다음 양 끝에 두 포인터를 둡니다. 매 단계에서 두 포인터가 가리키는 서로 다른 원소의 합을 후보로 보고, 지금까지의 최소 절댓값보다 작으면 두 인덱스를 저장합니다. 합이 음수이면 합을 키우기 위해 왼쪽 포인터를 오른쪽으로 옮기고, 양수이면 합을 줄이기 위해 오른쪽 포인터를 왼쪽으로 옮깁니다. 합이 0이면 절댓값을 더 줄일 수 없으므로 즉시 종료합니다.
모든 값이 같은 부호인 경우에도 같은 규칙으로 포인터가 진행하며 가능한 쌍을 확인합니다. 항상 left < right이므로 같은 원소를 두 번 선택하지 않습니다. 덧셈 전에 값을 long으로 확장하고, 절댓값 비교도 long 범위에서 수행해 큰 합의 오버플로를 피합니다. 정렬은 O(N log N), 투 포인터 순회는 O(N)이므로 전체 시간 복잡도는 O(N log N)이고, 정렬된 복사본을 위한 공간 복잡도는 O(N)입니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = input.nextInt();
}
Arrays.sort(values);
int left = 0;
int right = n - 1;
int bestLeft = left;
int bestRight = right;
long bestAbs = Long.MAX_VALUE;
while (left < right) {
long sum = (long) values[left] + values[right];
long absSum = Math.abs(sum);
if (absSum < bestAbs) {
bestAbs = absSum;
bestLeft = left;
bestRight = right;
}
if (sum == 0) {
break;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
System.out.println(values[bestLeft] + " " + values[bestRight]);
}
private static class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
int nextInt() throws IOException {
int c;
do {
c = input.read();
} while (c <= ' ' && c != -1);
int value = 0;
int sign = 1;
if (c == '-') {
sign = -1;
c = input.read();
}
while (c > ' ') {
value = value * 10 + c - '0';
c = input.read();
}
return sign * value;
}
}
}
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(BigInt);
const n = Number(input[0]);
const values = input.slice(1, n + 1).sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
let left = 0;
let right = n - 1;
let bestLeft = left;
let bestRight = right;
let bestAbs = null;
while (left < right) {
const sum = values[left] + values[right];
const absSum = sum < 0n ? -sum : sum;
if (bestAbs === null || absSum < bestAbs) {
bestAbs = absSum;
bestLeft = left;
bestRight = right;
}
if (sum === 0n) {
break;
} else if (sum < 0n) {
left++;
} else {
right--;
}
}
console.log(`${values[bestLeft]} ${values[bestRight]}`);
JavaScript에서는 BigInt를 사용해 덧셈과 절댓값 비교를 정확하게 처리합니다. 저장한 인덱스는 정렬된 배열에서 앞뒤 순서이므로 출력은 정렬된 두 값이며, 입력에서 서로 다른 두 원소입니다.